leetcode1145. 二叉树着色游戏

leetcode1145. 二叉树着色游戏

三月 14, 2020

leetcode1145. 二叉树着色游戏

有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中，给出二叉树的根节点 root，树上总共有 n 个节点，且 n 为奇数，其中每个节点上的值从 1 到 n 各不相同。

游戏从「一号」玩家开始（「一号」玩家为红色，「二号」玩家为蓝色），最开始时，
「一号」玩家从 [1, n] 中取一个值 x（1 <= x <= n）；
「二号」玩家也从 [1, n] 中取一个值 y（1 <= y <= n）且 y != x。
「一号」玩家给值为 x 的节点染上红色，而「二号」玩家给值为 y 的节点染上蓝色。

之后两位玩家轮流进行操作，每一回合，玩家选择一个他之前涂好颜色的节点，将所选节点一个 未着色 的邻节点（即左右子节点、或父节点）进行染色。
如果当前玩家无法找到这样的节点来染色时，他的回合就会被跳过。
若两个玩家都没有可以染色的节点时，游戏结束。着色节点最多的那位玩家获得胜利 ✌️。

现在，假设你是「二号」玩家，根据所给出的输入，假如存在一个 y 值可以确保你赢得这场游戏，则返回 true；若无法获胜，就请返回 false。

输入：root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3
输出：True
解释：第二个玩家可以选择值为 2 的节点。

思路

x这个人会把树分成三个部分,这个节点的左子树,右子树,和其余的节点.分析一下赢得条件,我要赢的话,必须在一开始堵住他的某一条路径(左右子树或者父节点).必须以这种情况下为前提,然后我的节点多,就可以获胜了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public int count=0;
    public TreeNode subRoot=null;
    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        traverse(root,x);//找到x涂色的位置
        int left=sum(subRoot.left,0);
        int right=sum(subRoot.right,0);    
        int all=n;
        //if((all-(left+right+1)>(left+right+1)))return true;
       // if(left>all-left)return true;
       // if(right>all-right)return true;
       // return false;这些可以直接这么写,酷炫
        return ((all-(left+right+1)>(left+right+1)))||left>all-left||right>all-right;
    }
    public void traverse(TreeNode root,int x){
        if(root==null)return;
        if(subRoot!=null)return;//这么就不用遍历整棵树了
        if(root.val==x){
            subRoot=root;
            return;
        }
        else{
            traverse(root.left,x);
            traverse(root.right,x);
        }  
    }
    public int sum(TreeNode root,int add){
        if(root==null)return 0;
        int tmp=add;
        add+=sum(root.left,tmp);
        add+=sum(root.right,tmp);
        add++;
        return add;
    }
}

leetcode 49/100