<jupyter_start><jupyter_text>说明：    有两位极客玩家参与了一场「二叉树着色」的游戏。    游戏中，给出二叉树的根节点 root，树上总共有 n 个节点，且 n 为奇数，其中每个节点上的值从 1 到 n 各不相同。    游戏从「一号」玩家开始（「一号」玩家为红色，「二号」玩家为蓝色），最开始时，    1、「一号」玩家从 [1, n] 中取一个值 x（1 <= x <= n）；    2、「二号」玩家也从 [1, n] 中取一个值 y（1 <= y <= n）且 y != x。    3、「一号」玩家给值为 x 的节点染上红色，而「二号」玩家给值为 y 的节点染上蓝色。    之后两位玩家轮流进行操作，每一回合，玩家选择一个他之前涂好颜色的节点，将所选节点一个 未着色 的邻节点（即左右子节点、或父节点）进行染色。    如果当前玩家无法找到这样的节点来染色时，他的回合就会被跳过。    若两个玩家都没有可以染色的节点时，游戏结束。    着色节点最多的那位玩家获得胜利 ✌️。    现在，假设你是「二号」玩家，根据所给出的输入，假如存在一个 y 值可以确保你赢得这场游戏，则返回 true；    若无法获胜，就请返回 false。提示：    1、二叉树的根节点为 root，树上由 n 个节点，节点上的值从 1 到 n 各不相同。    2、n 为奇数。    3、1 <= x <= n <= 100<jupyter_code><img src='https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/08/04/1480-binary-tree-coloring-game.png'>
<img src='1145.jpg'><jupyter_output><empty_output><jupyter_text>输入：root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3输出：True解释：第二个玩家可以选择值为 2 的节点。<jupyter_code># Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def btreeGameWinningMove(self, root: TreeNode, n: int, x: int) -> bool:
        t_root = self.find_target_root(root, x)
        r_count = self.count_elements(root) - self.count_elements(t_root) 
        t_l_count = self.count_elements(t_root.left)
        t_r_count = self.count_elements(t_root.right)
        if r_count > t_l_count + t_r_count or t_l_count > r_count + t_r_count or t_r_count > r_count + t_l_count:
            return True
        return False
    
    def find_target_root(self, root, x):
        if not root:
            return None
        if root.val == x:
            return root
        left = self.find_target_root(root.left, x)
        right = self.find_target_root(root.right, x)
        return left if left else right
        
    def count_elements(self, root):
        nodes = [root]
        count = 0
        while nodes:
            for _ in range(len(nodes)):
                node = nodes.pop()
                if node:
                    count += 1
                    if node.left:
                        nodes.append(node.left)
                    if node.right:
                        nodes.append(node.right)
        return count
def count_elements(node):
    if not node: return 0
    left = count_elements(node.left)
    right = count_elements(node.right)
    return 1+left+right<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1191919191919192, 'fraction_numerical': 0.02181818181818182, 'mean_word_length': 2.522048364153627, 'pattern_counts': {'":': 0, '<': 18, '<?xml version=': 0, '>': 15, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '547489', 'license': 'Apache-2.0', 'n_tokens_mistral': 1177, 'n_tokens_neox': 1259, 'n_words': 192, 'path': 'Tree/1022/1145. Binary Tree Coloring Game.ipynb', 'repo_name': 'YuHe0108/Leetcode', 'size': '2475'}