二叉树上的占领游戏

楼主举的例子对手选8，下面有8个点，自己选6只有上面7个点，还是对手赢吧？

MirandaChou 发表于 2019-3-22 06:32
楼主举的例子对手选8，下面有8个点，自己选6只有上面7个点，还是对手赢吧？

请再看看楼顶的树，8下面只有10，10下只有12，12下只有14. 所以8下面只有3个点。

微信用户_0x045 发表于 2019-3-9 05:13
嗯，找到一个结点，使以该结点为根的新树的左右子树结点数目相等或者相差不大于1。那么先手选此结点必然 ...

”使以该结点为根的新树的左右子树结点数目相等或者相差不大于1。那么先手选此结点必然不败“
难道只看这个节点的左右子树而不看它的parent吗？
我没太明白这个逻辑，可否再解释一下？

nnnnnnnn 发表于 2019-3-24 11:58
”使以该结点为根的新树的左右子树结点数目相等或者相差不大于1。那么先手选此结点必然不败“
难道只看 ...

我想错了。最坏（常见）的情况是变成一个三叉树，确实需要看左右子树和父结点三种情况。

狗家这道题，至今云里雾里

我觉得这道题是这个思路：
一棵二叉树，如果我的对手已经选中了某个节点node，接下来如果把这个节点从树中移除，那么这棵树会裂解成三个connected components:
A: node的left child
B: node的right child
C: 其他节点（如果node是root那这部分为空，否则这部分就是node的parent node及与其相连的节点们）

接下来我的选择就是在这个三个components中选择一个component作为我的领地，阻止对手在这个component扩张。为了最大化我的优势，我当然应该选择其中节点个数最多的。那么接下来我能不能赢得游戏就很好判断了：

如果其中存在某个component的节点数超过了原来整棵树的节点数的一半，那么我就可以选择这个component，然后我就赢了；否则我必输，因为即使我选择了节点最多的那个component，我和其他两个components之间被我的对手阻隔着，无法扩张到那里。

所以这题的解法就是数出ABC三个部分的节点数，最后return MAX(size(A), size(B), size(C)) > size(the whole tree) / 2

follow up也很简单，如果我决定了要选哪个component，那么下一步我就选择这个component里和node最近的那个，也就是node的parent/root of left child/root of right child.

补充内容 (2019-3-28 08:46):
java代码稍后补充

1. 
   
2. class Solution {
   
3.     public boolean findTreeNode(TreeNode root, TreeNode node) {
   
4.         int b = countNumberOfNodes(node.left);
   
5.         int c = countNumberOfNodes(node.right);
   
6.         int sum = countNumberOfNodes(root);
   
7.         int a = sum - 1 - b - c;
   
8.         return a > sum / 2 || b > sum / 2 || c > sum / 2;
   
9.     }
   
10.    
    
11.     private int countNumberOfNodes(TreeNode root) {
    
12.         if (root == null) {
    
13.             return 0;
    
14.         } else {
    
15.             return 1 + countNumberOfNodes(root.left) + countNumberOfNodes(root.right);
    
16.         }
    
17.     }
    
18. }
    

复制代码

Java代码基本是这样。不过有一个待改进的地方是，b和c两部分的节点数都数了两次，有点重复（虽然从时间复杂度上来说都是linear的）。也许把已经数过的部分记录下来会更好？

xueyi2017 发表于 2019-3-28 08:31
我觉得这道题是这个思路：
一棵二叉树，如果我的对手已经选中了某个节点node，接下来如果把这个节点从树中 ...

唔重新看了一遍题我觉得我follow up理解有偏差。。。如果是要我先选点并且要不败的话，那么基本思路应该还是数节点数：
1. 对于树中的每一个节点，我都数出以它为根的tree的节点数，并且储存起来。这一步可以用dp + hash table.
2. 接下来我可以通过1的结果进一步获得这样的数据：对于每一个节点，把它从树中移除、裂解生成的三个部分各自的节点数。
3. 如果存在某个节点A，删除它之后裂解生成的三个部分中没有哪一个部分的节点数超过了总节点数的半数，那么这个节点A就是我的不败节点。

楼主的例子里
‘如果你的对手选中了8，你选6就能胜利。而如果你选9，对手下一步可以由8扩张到6，对手就赢了。’
‘如果你的对手选中了8，你不是应该只能选6或者10吗？ 为什么9可以选。。

xueyi2017 发表于 2019-3-28 08:57
[mw_shl_code=java,true]
class Solution {
    public boolean findTreeNode(TreeNode root, TreeNode n ...

我觉得
return a > sum / 2 || b > sum / 2 || c > sum / 2;这个判断条件 在== sum/2 的时候返回false，那么是输。 但实际上也可能赢的。 所以这个条件只能判断 一部分可能赢，
题目问的判断是否能胜利？如下图在== sum/2 的情况也会赢，当然也可能会输，这个怎么弄？

补充内容 (2019-3-28 14:00):
中间一个，是平手，不输不赢？

补充内容 (2019-3-28 14:34):
我弄错了。。 ==sum/2 只可能是平手了，赢不了。