这题还是有点意思的，因为只能从第一个染色节点开始拓展，所以作为后手的B，一定是将A的第一个染色节点的父亲或者两个儿子染色，堵住A的路，这样才有可能获胜。

 

所以B占据的区域要么是除A占据的子树以外的部分，要么就是A的第一个染色节点的左子树或者右子树，只有这三种情况.

所以我们计算一下A的第一个染色节点的左子树和右子树的节点个数，就可以得知

1、左子树的节点个数，

2、右子树的节点个数

3、A的第一个染色节点的子树的节点个数

4、除A的第一个染色节点的子树的节点其余节点的个数

 

如果

1、左子树的节点个数比其余地方的节点个数多

2、右子树的节点个数比其余地方的节点个数多

3、彻底放弃A的第一个染色节点的子树，其他区域的节点个数比A的第一个染色节点的子树的节点个数多

就能获胜，除此以外都不能获胜.

1 class Solution 2 { 3     public: 4         int f(TreeNode* root) 5         { 6             if(!root) return 0; 7             return f(root->left)+f(root->right)+1; 8         } 9         TreeNode* preorder(TreeNode *root,int x)10         {11             if(!root) return NULL;12             if(root->val==x)13                 return root;14             TreeNode *t1 = preorder(root->left,x);15             TreeNode *t2 = preorder(root->right,x);16             if(t1) return t1;17             else if(t2) return t2;18             return NULL;19         }20         bool btreeGameWinningMove(TreeNode* root, int n, int x)21         {22             TreeNode* t = preorder(root,x);23             int k1 = f(t->left);24             int k2 = f(t->right);25             //k1 > n-k1 || k2 > n-k2 || n-k1-k2-1 > k1+k2+1 分别对应题解中三种情况26             if(max(2*k1,2*k2)>n || n>2*(k1+k2+1))27                 return true;28             return false;29         }30 };