二叉树上的占领游戏

ygmm 发表于 2019-3-28 13:58
我觉得
return a > sum / 2 || b > sum / 2 || c > sum / 2;这个判断条件 在== sum/2 的时候返回false ...

我觉得可以这么弄

1. int myPoint = Math.max(a,Math.max(b,c));
   
2. return myPoint > sum - myPoint;

复制代码

我把对手紧挨着的最大path给堵住了，那么对手只能走剩下的最小path；如果最大path小于其余path和的话那么就是false;

ygmm 发表于 2019-4-14 12:40
有谁知道leetcode 题号？

请参考芭伞肆，原题是统计距离，计数那部分对这题挺有帮助的

思路是用个map来存左右子树的节点，避免重复计算。
根据树的结构不同先手好像没有必胜的方法，只能说保证不败，会出现平局的情况。比如下面这颗树
│       ┌── 7
│       │   └── 12
│   ┌── 3
│   │   │   ┌── 11
│   │   └── 6
│   │       └── 10
└── 1
    │   ┌── 5
    └── 2
        │   ┌── 9
        └── 4
            └── 8
[3, 1]

1. class solution{
   
2.     Map<TreeNode,int[]> map = new HashMap<>();
   
3.     public boolean findTreeNode(TreeNode root, TreeNode node) {
   
4.         int sum = countNumberOfNodes(root);
   
5.         int[] temp = map.get(root);
   
6.         int b = temp[0];
   
7.         int c = temp[1];
   
8.         int a = sum - 1 - b - c;
   
9.         return a > sum / 2 || b > sum / 2 || c > sum / 2;
   
10. }
    
11.     public List<Integer> win(TreeNode root){
    
12.         List<Integer> res = new ArrayList<>();
    
13.         int[] temp = map.get(root);
    
14.         int sum = temp[0]+temp[1]+1;
    
15.         for(TreeNode node : map.keySet()){
    
16.             int[] num = map.get(node);
    
17.             int l = num[0], r = num[1];
    
18.             int a = sum - 1 - l - r;
    
19.             if(a <= sum/2 && r <= sum/2 && l <= sum/2){
    
20.                 res.add(node.val);
    
21.             }
    
22.         }
    
23.         return res;
    
24.     }
    
25.     public int countNumberOfNodes(TreeNode root) {
    
26.         if (root == null) {
    
27.             return 0;
    
28.         } else {
    
29.             int a = countNumberOfNodes(root.left);
    
30.             int b = countNumberOfNodes(root.right);
    
31.             map.put(root,new int[]{a,b});
    
32.             return 1+a+b;
    
33.         }
    
34. }
    
35.     }

复制代码