题目描述
思路解析
一句话答案：LeetCode 1145 二叉树着色游戏：x 把树切成左子树、右子树、父亲方向三块，二号堵最大那块，最大块严格＞n//2 就赢——一趟 DFS 数子树即可判，时间 O(n)。
选完 x，二号还有没有机会染得更多
树上 n 个节点、n 是奇数，值 1 到 n 互不相同。一号先挑值 x 的节点染红，二号挑另一个值 y 染蓝，之后轮流把自己染过节点的未染相邻节点（左、右孩子或父节点）接着染，谁都动不了才结束，染得多的赢。问能否找到 y 让二号多于一号。题面两例：root=[1,2,3,4,5,6,7,8,9,10,11]、x=3 返 true，root=[1,2,3]、x=1 返 false。
真把这盘棋一回合回合走完，会卡在哪
照规则把染色模拟一遍是最像直觉的打算：每选一个 y 就推演整局看谁多。可 y 有 n-1 种选法，每种都要模拟到填满棋盘，慢且易在蔓延顺序上错。它更漏了个一步定音的事实：x 一落下，胜负就已锁死。
x 一落子，棋就被切成互不相通的三块
x 这个节点是一堵墙：从它出发只有左子树、右子树、父亲往上三个方向，块与块之间的唯一通道都要过 x，而 x 归了一号，谁也穿不过去。所以二号把 y 紧贴 x 放，就能独占某一整块。
二号最多能拿三块里最大的一块，大小分别是左子树节点数 l、右子树节点数 r、父亲方向 n-l-r-1（刨去 x 和其左右子树）。判赢要最大块严格＞n//2：n 是奇数没平局，最大块恰好等于 n//2 时二号也没过半，剩下都归一号。
代码只做两件事：找到 x，数它的左右子树
先一趟 DFS，也就是深搜、顺一条路走到底再回头，找值等于 x 的节点：遇空或命中就返回，否则先左后右（Python 的 dfs(left) or dfs(right) 靠短路，左边有就不看右边）。拿到 x 后各数一遍左右子树得 l、r，父亲方向不必数，用 n-l-r-1 减出。最后 max(l, r, n-l-r-1) 与 n//2 比，大于返回 true。
两个题面例子，各自量出三块
root=[1,2,3,4,5,6,7,8,9,10,11]、x=3：按层序摆开，3 是根 1 的右孩子，左孩子 6、右孩子 7 都是叶子。左子树只有 6，l=1；右子树只有 7，r=1；父亲方向 11-1-1-1=8。三块是 1、1、8，最大 8；n//2=5，8＞5，返回 true。
root=[1,2,3]、x=1：根就是 x，左右孩子 2、3 各是一个叶子，l=1、r=1；x 是根、头顶没有节点，父亲方向 3-1-1-1=0。三块是 1、1、0，最大 1；n//2=1，最大块 1 并没有严格＞1，返回 false。这正是打平半数、二号赢不了的情形：占个叶子，反被守根的一号多染一个。
算得快不是难点，难在别把三块漏了一块
复杂度：找 x 最坏扫遍全树 O(n)，数子树也不超过 O(n)，合起来仍是 O(n)。占空间的是递归栈、深度等于树高：平衡时约 O(log n)，退化成链时 O(n)。
几处一写就反：只比左右子树、忘了父亲方向那块，可它常常最大，漏掉会把能赢判成不能赢；判赢用大于等于 n//2，会在最大块恰好等于半数时误判二号赢。边角想清：n=1 时二号无子可染永远 false，x 是叶子时父亲方向独占 n-1 个、多半稳赢。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这一句:x 把树切成左子树、右子树、父亲方向三块,二号去堵最大的一块,只要它比 n 的一半还大就赢。下面每一帧都在量这三块。
全局 · 这棵树长这样：先看清这棵树。一共 11 个节点,值是 1 到 11 互不相同的整数(题目规定值是 1 到 n 的排列)。游戏规则是一号先在某个节点上落子,你二号再落一子,然后轮流向相邻节点蔓延。现在轮到一号先选了。
一号落子 · 染红值为 3 的节点：一号把值为 3 的节点染了色,就是橙色这个。注意它一落子,整棵树就被它隔成了三块互不相通的区域:它的左子树、它的右子树、以及从它往上通向父亲的那一大片。我们要做的就是量清楚这三块各有多大。
定位 x · 从根 6 出发：先得在树里把这个 x 找出来。从根 6 开始一路深搜:根的值是 6,不是我们要的 3,那就往孩子走,先去左边看看。
定位 x · 在左孩子找到 3：走到根的左孩子,值正好是 3,这就是一号落子的 x,锁定它。接下来分别量它的左子树、右子树,再算父亲方向那一块。
量左子树 · 进到左孩子 2：先量左子树。从 3 的左孩子 2 进去,这一整块以后都归左子树。计数器 l 先记成 0,每数到一个节点就加一。
量左子树 · 数到 2,l = 1：节点 2 算进左子树,l 变成 1,把它标成蓝色表示已经数过。再看看节点 2 下面还有没有节点,有的话接着数。
量左子树 · 走到叶子 1：节点 2 还有个左孩子 1,走下去。1 是叶子,下面再没有节点了,但它仍然属于左子树,也得数进去。
量左子树 · 数到 1,l = 2：节点 1 算进去,l 变成 2。节点 1 没有孩子了,左子树这一支也就到头了。
左子树量完 · l = 2：左子树数完了,一共节点 2 和 1 两个节点,l 等于 2。蓝色这一小块就是二号如果选左孩子能独占的区域。记住这个 2,接着量右边。
量右子树 · 进到右孩子 4：再量右子树。左块的蓝色先留着别动,从 3 的右孩子 4 进去,计数器 r 从 0 起步,同样数一个加一个。
量右子树 · 数到 4,r = 1：节点 4 算进右子树,r 变成 1,把它标成绿色,跟左块的蓝色区分开。再看节点 4 下面还挂着谁。
量右子树 · 走到叶子 5：节点 4 有个右孩子 5,走下去。5 也是叶子,下面没有别的节点,但它仍归右子树,继续数进去。
量右子树 · 数到 5,r = 2：节点 5 算进去,r 变成 2。节点 5 没有孩子,右子树这一支也到头了。
右子树量完 · r = 2：右子树数完,节点 4 和 5 两个,r 等于 2。绿色这一块就是二号如果选右孩子能独占的区域。现在左块 2、右块 2,只剩最后一块还没算。
x 的地盘 · 1 + l + r = 5：把 x 自己,加上它的左子树和右子树,1 加 2 加 2 等于 5,这 5 个节点是「x 这一坨」。整棵树 11 个,刨掉这 5 个,剩下的全都在 x 往上的父亲方向。
父亲方向 · n - l - r - 1 = 6：父亲方向那一块不用一个个数,直接用总数 11 减掉 x 这一坨 5,等于 6。也就是图上那 6 个还没上色的节点:6、9、7、10、8、11,它们都在 x 的上方。
三块到齐 · 左 2 · 右 2 · 父亲 6：三块全量出来了:左子树 2 个,右子树 2 个,父亲方向 6 个。一眼就看出来,父亲方向那块最大。二号要赢,就该往最大的这块去堵。
和一半比 · max = 6,半数 = 5：取三块里最大的 6,再看 n 的一半:11 除以 2 向下取整是 5。6 严格大于 5,说明只要二号占住父亲方向那 6 个,就已经过了半数,这局稳赢。
二号必胜手 · y 贴在 3 的父亲 6：具体怎么落子?二号把 y 放在 3 的父亲、也就是根 6 上。这一子像一道闸门,把一号死死封在它自己那 5 个节点里,而二号顺着父亲方向能把那 6 个全染蓝。
收束 · 6 > 5,返回 true：最后一清点:二号 6 个,一号 5 个,6 比 5 多,二号赢。所以这道题答案是 true。整个过程没真去模拟一回合一回合的染色,只靠量出三块、堵最大那块,一步就判了输赢。
回放 · 必胜的关键就一句：回放一遍:x 把树切成 2、2、6 三块,最大的一块 6 超过了一半,二号就把 y 贴在那一块的入口堵上,稳赢。要是三块最大的都不过半,那二号怎么下都赢不了,返回 false。
边界先想清:单节点二号没法赢;x 在根时父亲方向为 0;x 是叶子时父亲方向最大,常常一举过半。
面试重点:y 贴着 x 堵死通道所以独占整块、判赢要严格大于半数(n 是奇数)、定位 x 一次即可不必逐个模拟。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next# 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 = rightclass Solution: def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool: def dfs(root): if root is None or root.val == x: return root return dfs(root.left) or dfs(root.right) def count(root): if root is None: return 0 return 1 + count(root.left) + count(root.right) node = dfs(root) l, r = count(node.left), count(node.right) return max(l, r, n - l - r - 1) > n // 2复杂度
- 时间：O(n)，找 x 的 dfs 最坏扫遍全树 O(n);找到后数左右子树合计也只覆盖 x 子树里的节点,不超过 O(n)。两段相加仍是 O(n),n 是节点总数
- 空间：O(h)，只用了几个整数变量,额外结构没有;真正占空间的是递归栈,深度等于树高 h。平衡树约 O(log n),退化成链时最坏 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么二号把 y 紧贴 x 放,就能独占一整块、而不会被一号抢走?
追问为什么是和 n 除以 2 比,而且要严格大于?
追问能不能不去找 x、直接对每个节点试一遍?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最大层内元素和
LeetCode 1161 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题