题目描述
思路解析动画文字版
记牢这一句: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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题