1145. 二叉树着色游戏

有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中，给出二叉树的根节点 root，树上总共有 n 个节点，且 n 为奇数，其中每个节点上的值从 1 到 n 各不相同。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-tree-coloring-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
写的第一版，超时了，嘿嘿。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def btreeGameWinningMove(self, root, n, x):
        """
        :type root: TreeNode
        :type n: int
        :type x: int
        :rtype: bool
        """
        def searching(root):
            _foreach = deque([root])
            node_nums = 0
            while _foreach:
                for _ in range(len(_foreach)):
                    _current_node = _foreach.pop()
                    node_nums += 1
                    for node in [_current_node.left,_current_node.right]:
                        if node:
                            _foreach.appendleft(_current_node)
            return node_nums

        foreach = deque([root])
        while foreach:
            for _ in range(len(foreach)):
                current_node = foreach.pop()
                if current_node.val == x:
                    # if current_node.left:
                    left_num = searching(current_node.left) 
                    if current_node.right:
                        right_num = searching(current_node.left) 
                    if left_num and right_num:
                        return True
                    else:
                        return False
                if current_node.left.val == x:
                    left_num = searching(current_node.left)
                    right_num = searching(current_node.right)
                    if right_num > left_num:
                        return True
                    else:
                        return False
                if current_node.right.val == x:
                    left_num = searching(current_node.left)
                    right_num = searching(current_node.right)
                    if left_num > right_num:
                        return True
                    else:
                        return False

后来发现searching写的有问题，不应该写循环，可是还是没通过，嘿嘿。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def btreeGameWinningMove(self, root, n, x):
        """
        :type root: TreeNode
        :type n: int
        :type x: int
        :rtype: bool
        """
        def searching(root):
            node_nums = 0
            if root:
                node_nums += 1
                left_num = searching(root.left)
                right_num = searching(root.right)
                node_nums += left_num + right_num
            return node_nums

        foreach = deque([root])
        while foreach:
            for _ in range(len(foreach)):
                current_node = foreach.pop()
                if current_node.val == x:
                    print("current:")
                    # if current_node.left:
                    left_num = searching(current_node.left) 
                    right_num = searching(current_node.right)
                    print(left_num,right_num)
                    # if left_num > (n - 1)  or right_num > (n - 1) :
                    if left_num > (right_num + 1) or right_num > (left_num + 1) :
                        return True
                    else:
                        return False
                if current_node.left and current_node.left.val == x:
                    print("left:")
                    left_num = searching(current_node.left)
                    right_num = searching(current_node.right)
                    print(left_num,right_num,left_num>right_num)
                    if (right_num + 1) > left_num:
                        return True
                    else:
                        return False
                if current_node.right and current_node.right.val == x:
                    print("right:")
                    left_num = searching(current_node.left)
                    right_num = searching(current_node.right)
                    print(left_num,right_num)
                    if (left_num + 1) > right_num:
                        return True
                    else:
                        return False
                if current_node.left:
                    foreach.appendleft(current_node.left)
                if current_node.right:
                    foreach.appendleft(current_node.right)

贴一个评论区的解决方案，没太看懂，嘿嘿。

class Solution {
public:
int Lcnt;
int Rcnt;
int count(TreeNode* root)
{
    int cnt = 0;
    if(root)
    {
        cnt++;
        int Lc = count(root->left);
        int Rc = count(root->right);
        cnt += Lc + Rc;
    }
    return cnt;
}
void dfs(TreeNode* root,int x)
{
    if(root)
    {
        if(root->val == x)
        {
            Lcnt = count(root->left);
            Rcnt = count(root->right);
        }
        else
        {
            dfs(root->left,x);
            dfs(root->right,x);
        }
    }
}
bool btreeGameWinningMove(TreeNode* root, int n, int x) 
{
    dfs(root,x);
    if(n > 2 * (Lcnt + Rcnt + 1))return true;
    if(2 * Lcnt > n)return true;
    if(2 * Rcnt > n)return true;
    return false;
}
};