Skip to content

1145. Binary Tree Coloring Game 👍

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  bool btreeGameWinningMove(TreeNode* root, int n, int x) {
    count(root, x);
    return max({leftCount, rightCount, n - leftCount - rightCount - 1}) > n / 2;
  }

 private:
  int leftCount;   // the number of nodes of n's left
  int rightCount;  // the number of nodes of n's right

  int count(TreeNode* root, int x) {
    if (root == nullptr)
      return 0;
    const int l = count(root->left, x);
    const int r = count(root->right, x);
    if (root->val == x) {
      leftCount = l;
      rightCount = r;
    }
    return 1 + l + r;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
    count(root, x);
    return Math.max(Math.max(leftCount, rightCount), n - leftCount - rightCount - 1) > n / 2;
  }

  private int leftCount;  // the number of nodes of n's left
  private int rightCount; // the number of nodes of n's right

  private int count(TreeNode root, int x) {
    if (root == null)
      return 0;
    final int l = count(root.left, x);
    final int r = count(root.right, x);
    if (root.val == x) {
      leftCount = l;
      rightCount = r;
    }
    return 1 + l + r;
  }
}