二叉树上的占领游戏
在一棵二叉树上玩一个游戏，对手先选择树上一个节点，现在该由你来选择一个点。然后同时开始，从选择的那个点开始，
向外扩张，只可以去占领其相邻的点(parent and children)，然后从占领的点再去扩张，依次类推，
但如果相邻的点已经被对方占了，就没法去占领了。谁最终占有的点最多谁获胜。
input是树root和对手选中的node,返回你是否能胜利
followup 如果你先选择点，你该选择哪个点能胜利？
比如下面这个树，如果你的对手选中了8，你选6就能胜利。而如果你选9，对手下一步可以由8扩张到6，对手就赢了。
https://www.1point3acres.com/bbs ... read&tid=488670
嗯，找到一个结点，使以该结点为根的新树的左右子树结点数目相等或者相差不大于1。那么先手选此结点必然不败；如果新树左右子树结点数目相等则先手胜，否则先手平。
在一棵二叉树上玩一个游戏，对手先选择树上一个节点，现在该由你来选择一个点。然后同时开始，从选择的那个点开始，
向外扩张，只可以去占领其相邻的点(parent and children)，然后从占领的点再去扩张，依次类推，
但如果相邻的点已经被对方占了，就没法去占领了。谁最终占有的点最多谁获胜。
input是树root和对手选中的node,返回你是否能胜利
followup 如果你先选择点，你该选择哪个点能胜利？
比如下面这个树，如果你的对手选中了8，你选6就能胜利。而如果你选9，对手下一步可以由8扩张到6，对手就赢了。
1 2 3 4 5 67 8 9 10 11 12 13 14 15 |
不是一次。turn-based选。比如楼上的树，我选1，你选3。因为规则是必须从占领的点相邻的扩张。我占领的点是【1】。而3你又占着，所以我只能选2来扩张.
你选了某个点i，那么对方肯定选跟i相临的某个点。
所以对方就是选了以点i为root，权值和最大的一个subtree。
先选的一方肯定是不败的。
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=488670
https://docs.google.com/document/d/1qxA2wps0IhVRWULulQ55W4SGPMu2AE5MkBB37h8Dr58/
https://docs.google.com/document/d/1qxA2wps0IhVRWULulQ55W4SGPMu2AE5MkBB37h8Dr58/
红蓝小人占领二叉树 （频率 5）
两个人红蓝，在二叉树上，每个人可以从第一个选的点开始同时往相邻的点扩展占领点，已知red选了一个点，（规则大概是两点之间的可以共同占领，但红的children只能红的占）问蓝第一个点选哪里最后能占领的最多。输入root和红的点，输出蓝色选的node
请问这题可以有哪位好心的童鞋再解释一下题目的意思吗？“规则大概是两点之间的可以共同占领，但红的children只能红的占” 这里看不懂😔
例子：(N： 空node， r: 红色点，b蓝色点)
n
/ \
n n
n r n n
n n n n n n n n
如果蓝色小人在红色小人上方作为起点，标红点node现在对于蓝色小人来说永远不可占领，其他节点两人可以轮流扩展占领
此处b选在蓝色节点处为最佳策略，蓝色小人堵住了红色小人向上扩展的机会
思路：
这个题关键在于明白规则：
即出了第一个点，其余的点放的时候都要连接到相同颜色的点， 所以红色选定后，就把树分为了三部分，如果蓝色选的是最大的一部分并且紧挨着红色第一个点，就有可能赢。 因为最大的一部分被蓝色堵住后， 红色都到不了了
选第一个点的的时候，要选一个三部分尽量均匀的，即 任何两部分都大于第三部分的，即红色先选并选第一个点的规则， 这个是follow up
参考代码
Provider: null
TreeNode {
int key;
TreeNode left;
TreeNode right;
public TreeNode(int key) {this.key = key;}
}
private TreeNode redParent = null;
private TreeNode red = null;
public TreeNode findNode(TreeNode root, TreeNode red) {
// sanity check
this.red = red;
int redL = countNode(red.left);
int redR = countNode(red.right);
int redParent = countNode(root);
int max = Math.max(redParent, Math.max(redL, redR));
if(max == redL) return red.left;
else if(max == redR) return red.right;
else return redParent;
}
private int countNode(TreeNode root) {
if(root.left == red || root.right == red) redParent = root;
if(root == null || root == red) return 0;
return countNode(root.left) + 1 + countNode(root.right);
}
