Binary Tree Coloring Game LeetCode solution in C++

1
class Solution {
2
 public:
3
  // nodex means "node with val = x"
4
  // Idea behind this is to block either nodex's parent or it's left child or
5
  // right child. Block means we will chose that node as nodey. Why? because it
6
  // will devide the tree in two parts, one for player 1 and other for player 2.
7
  // Then we have to just take the maximum no of nodes we can get, from these
8
  // three nodes as head, and if max is greater than n/2, means we can will.
9
  TreeNode *nodex, *parentx;
10
  Solution() {
11
    nodex = NULL;
12
    parentx = NULL;
13
  }
14
  int count(TreeNode *root) {
15
    if (root == NULL) return 0;
16
    int a = count(root->left);
17
    int b = count(root->right);
18
    return a + b + 1;
19
  }
20
  bool findx(TreeNode *root, int x) {
21
    if (root == NULL) return false;
22
    parentx = root;
23
    if (root->val == x) {
24
      nodex = root;
25
      return true;
26
    }
27
    bool a = findx(root->left, x);
28
    if (a) return true;
29
    bool b = findx(root->right, x);
30
    return b;
31
  }
32
  bool btreeGameWinningMove(TreeNode *root, int n, int x) {
33
    findx(root, x);              // Find the node which has val = x
34
    int p = n - count(nodex);    // Count the no of nodes of blue color, if we
35
                                 // decide to take parent of nodex as nodey
36
    int r = count(nodex->right); // Count the no of nodes of blue color, if we
37
                                 // decide to take right child of nodex as nodey
38
    int l = count(nodex->left);  // Count the no of nodes of blue color, if we
39
                                 // decide to take left child of nodex as nodey
40
    int mx = max(p, r);
41
    mx = max(mx, l); // max of all three possible scenarios
42
    if (mx > n / 2)
43
      return true;
44
    else
45
      return false;
46
  }
47
};