• Time:O(n)
• Space:O(h)

## C++

``````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;   // # of nodes of n's left
int rightCount;  // # of nodes of n's right

int count(TreeNode* root, int x) {
if (!root)
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;
}
};
``````

## JAVA

``````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;  // # of nodes of n's left
private int rightCount; // # 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;
}
}
``````