刷LeetCode刷到Easy题很多人的心态就是“看一眼答案过了就完事”。但单值二叉树这道题我建议你认真手动写一遍——它是我见过的把递归三要素体现得最干净的小题之一。判断一棵二叉树是不是“单值”所有节点的值都相同用递归解核心代码只需要五六行却能把终止条件、子问题拆分、短路逻辑全讲明白。这篇文章就从这题出发把递归解法从原理到代码、从复杂度到与迭代方案的对比完整拆一遍。适合刚学树结构的人也适合准备面试但想巩固递归基础的选手。1. 单值二叉树到底是什么题目语义与边界条件拆解1.1 定义梳理一棵树所有节点值相同单值二叉树Univalued Binary Tree的定义非常直白给定一棵二叉树如果每个节点具有相同的值那么它就是单值二叉树。举个例子一棵树的所有节点值都是5那它算单值只要出现一个节点的值是6整棵树立刻不算。这个定义最容易被忽视的点是判断的不是“相邻节点值相同”而是“所有节点值相同”。虽然两者在树结构里是等价的但理解角度不同写出的代码风格完全不同。我的建议是把它想象成整栋楼的检查你要确认每个房间的灯泡型号一样不需要把所有灯泡拆下来堆在一起对比只需要沿着走廊挨个看只要发现有一间房和邻居不一样整栋楼就可以直接下结论“不合格”。单值二叉树的判断也是这个逻辑。1.2 边界条件的“坑”空树到底算不算单值第一次写这道题的人几乎都会在空树这里卡一下。空树没有任何节点它的“值”是什么不同的人会有不同的第一反应有人觉得应该返回false有人觉得应该返回true。实际题目约定很明确空树返回true。为什么你可以把它理解成数学上的“真空真”vacuous truth如果树为空那么“所有节点值相同”这个命题没有被任何反例推翻所以命题成立。更实际的理由是递归解法需要一个干净的终止条件。如果空树返回false那所有非空树的递归都会在叶子节点处断裂比如一个单节点树它的左右孩子都是空递归到空节点返回false整棵树反而变成了false这明显不对。所以在代码里第一个if一定是if root is None: return True这个base case是整个递归的基石也是很多Easy题考察的细节之一。1.3 单节点和左右子树组合的直觉判断单节点树必然是单值因为只有一个节点不存在“不同”的比较对象。两个节点的树只要父子值相同就是单值。三个节点的树除了根节点还要保证左右两个子树各自都是单值的。从这里可以提炼出一个递归式一棵树是单值的当且仅当根节点与左孩子值相同且根节点与右孩子值相同且左子树是单值且右子树是单值。这个“且”字非常关键。任何一个条件不满足结果就是false。这也是后面写递归时的核心逻辑。2. 递归解法的直觉来自树的递归定义2.1 为什么“判断单值”天然适合递归二叉树本身就是递归定义的它由一个根节点和左子树、右子树组成而左右子树仍然是二叉树。这意味着处理一棵树的问题通常可以拆成“处理根节点 处理左子树 处理右子树”三个子问题左右子树的处理方式和整棵树完全一样。单值判断正好匹配这种结构。判断整棵树是否单值等价于先判断根节点和左右孩子是否相等再递归判断左右子树是否单值。你可以直接把这个定义翻译成代码不需要额外的状态记录。这里也是递归和普通循环思维差异最大的地方循环强调“维护一个变量不断推进”递归强调“用子问题的解组合出原问题的解”。单值二叉树判断是理解这种思维切换的绝佳入门题。2.2 递归三要素在本题里的具体映射写任何递归我都建议先问自己三个问题终止条件是什么当前节点需要做什么子问题之间如何组合结果对应到单值二叉树终止条件节点为空返回true。当前节点要做的事检查当前节点和左孩子如果存在是否等值检查当前节点和右孩子如果存在是否等值。子问题组合左子树的结果和右子树的结果用and连接同时还要和当前层的比较结果做and。这三步想清楚代码就是顺着写下来的。很多人写递归容易乱根源是没想清楚“当前层做什么”总想把所有事都塞给递归调用导致逻辑越写越绕。2.3 判断顺序与短路逻辑为什么要尽早返回递归的判断顺序有讲究。最自然的写法是在当前层先做“父节点 vs 孩子节点”的比较只要有一处不等立即返回false不再深入递归。看一下这段代码def is_unival_tree(root): if root is None: return True if root.left and root.left.val ! root.val: return False if root.right and root.right.val ! root.val: return False return is_unival_tree(root.left) and is_unival_tree(root.right)当左子树已经返回false时and右侧的is_unival_tree(root.right)根本不会执行这就是短路。如果一棵树的第二层就出现了不同值后面的节点根本不会被访问省下大量无谓的递归调用。有些人的写法是“先递归左右子树再比较值”这在正确性上也没问题但会无谓地遍历完整棵树。在面试中主动提一句短路优化通常能让面试官觉得你对递归的执行机制有真实理解。3. 手写代码核心实现与参数设计3.1 最直观的版本当前节点与孩子值比较上面那段就是最直观的写法直接在函数内部比较root和左右孩子的值。它的优点是语义清楚不需要额外参数缺点是比较逻辑分散在“前奏判断”和“递归调用”两步中代码一多容易看乱。这个版本还有一个好处入口不需要判空之外的任何准备空树直接返回true非空树从根开始一路向下比。3.2 目标值传递版本DFS加闭包另一种常见思路是先取出根节点的值作为目标值target然后写一个辅助的DFS函数遍历过程中检查每个节点的值是否等于target。def is_unival_tree(root): if root is None: return True target root.val def dfs(node): if node is None: return True if node.val ! target: return False return dfs(node.left) and dfs(node.right) return dfs(root)这个版本的代码非常对称入口判空取出目标值辅助函数负责遍历。它的缺点是闭包里绑定了一个外部变量如果哪天你想复用一个检查函数来判断“任意目标值”还得改造。3.3 双参数递归把目标值一路传下去还有一种在题解区很常见的写法递归函数接收一个val参数每一层都把当前节点的值作为新的目标传给下一层。def is_unival_tree(root): if root is None: return True def dfs(node, val): if node is None: return True if node.val ! val: return False return dfs(node.left, node.val) and dfs(node.right, node.val) return dfs(root, root.val)这里的关键点是虽然参数val不断变化但判断逻辑依然正确。因为单值树的等价定义是所有父子边两端的值都相等。只要每条父子边都满足相等整棵树必然所有节点同值。所以每层把当前节点值传下去等于逐条检查父子边最终结果和固定target完全一致。Java版本也顺手贴一下入口判空那里最容易踩NPEpublic boolean isUnivalTree(TreeNode root) { if (root null) return true; return dfs(root, root.val); } private boolean dfs(TreeNode node, int val) { if (node null) return true; if (node.val ! val) return false; return dfs(node.left, node.val) dfs(node.right, node.val); }3.4 全局变量写法的隐藏风险我也见过有人用全局变量记录结果遍历时一旦发现不同就置位flag True def dfs(node, target): global flag if node is None or not flag: return if node.val ! target: flag False return dfs(node.left, target) dfs(node.right, target)这种写法能通过测试但我不推荐。全局变量在并发、多次调用、嵌套调用场景下很容易残留状态导致“上一次调用的结果污染下一次判断”。而且它破坏了递归函数的纯度——函数不再通过返回值表达结果而是靠外部副作用。面试中如果写成这样至少会被追问一轮“你觉得这样有什么问题”。三种“正规”写法各有偏好我平时的选择是如果只是刷题用当前节点与孩子比较的版本代码最短如果在生产代码里需要一个可复用的判断工具用双参数版本语义边界清晰。4. 复杂度分析与极端测试为什么这个解法是O(n)4.1 时间复杂度每个节点访问一次递归版本的时间复杂度是O(n)n是树的节点总数。理由很简单每个非空节点只会作为“当前节点”被处理一次每次处理只做常数次比较和值获取然后向左右子树递归。不存在某个节点被重复访问的情况。这里有个容易被忽略的细节由于短路逻辑如果一棵树在很靠上的位置就发现了不等实际访问的节点数会远小于n。但复杂度分析看的是最坏情况——当整棵树确实单值时没有任何提前返回发生必须访问全部节点所以最坏时间复杂度就是O(n)。4.2 空间复杂度递归调用栈占用O(h)递归版本真正的成本在空间上。每次函数调用都会在系统调用栈上压入一层帧深度等于当前递归链的长度也就是树的高度h。平衡二叉树h O(log n)空间复杂度O(log n)。退化成链表的树h O(n)空间复杂度O(n)。很多刚学递归的人只记得“递归有栈溢出风险”但不知道来源。栈深度就是函数嵌套调用层数写一个10000层的链表树递归必然爆栈。面试时能主动说出“空间复杂度不是O(1)而是O(h)”是很加分的细节。4.3 实测边界输入清单我每次写完树相关代码都会跑一遍下面的输入覆盖所有容易出问题的分支输入树结构预期结果说明空树truebase case单节点 [5]true没有比较对象[1, 1, 1]true简单全等[1, 1, 2]false右孩子不等[1, null, 2]false斜树非空右孩子不等[2, 2, 2, 2, null, 2, 2]true多层全等[2, 2, 2, 3, null, 2, 2]false左子树内部有不等其中[1, null, 2]这个输入是专门用来测“当前节点只和存在的孩子比较”的分支逻辑的。如果代码里没写root.right的存在性判断直接访问root.right.val在这里就会抛空指针。4.4 深度很大的树会触发递归上限Python默认递归深度通常是1000层左右。如果测试用例是一棵10000层的链状树递归版本会直接抛出RecursionError。有两种应对方向一是临时调大递归上限比如sys.setrecursionlimit(20000)但这是治标不治本二是把递归改写成显式栈的迭代版本这也是下一节要展开的内容。5. 递归与迭代的对比不只是“栈溢出”那么简单5.1 递归的开销到底在哪递归代码简洁但每次调用都要经历“压栈、传参、跳转、返回、弹栈”一整套流程函数调用框架本身有时间和空间成本。在Python里递归调用的常数开销尤其明显同样的算法递归版通常比迭代版慢一些。而且Python没有做尾递归优化哪怕你的递归写成了尾调用形式深度依然会累积。单值判断这种“带有提前返回分支”的逻辑递归代码其实并不比迭代短多少。这时候最理性的选择是如果树的深度可能很大直接上迭代别逞强。5.2 迭代写法BFS队列和DFS显式栈迭代版单值判断的核心思想是用显式容器管理“待访问节点”。BFS用队列from collections import deque def is_unival_tree_iterative(root): if root is None: return True target root.val q deque([root]) while q: node q.popleft() if node.val ! target: return False if node.left: q.append(node.left) if node.right: q.append(node.right) return TrueDFS用显式栈def is_unival_tree_iterative_stack(root): if root is None: return True target root.val stack [root] while stack: node stack.pop() if node.val ! target: return False if node.right: stack.append(node.right) if node.left: stack.append(node.left) return True两个版本的时间复杂度都是O(n)空间复杂度都是O(n)。队列版最差情况要容纳一整层节点栈版最差情况接近树高。两个版本都不受递归深度限制链状树也能放心跑。5.3 用阶乘和快速排序理解递归与迭代的本质区别递归和迭代最经典的对比例子是阶乘。递归版本fact(n) n * fact(n-1)依赖“用子问题表达当前问题”迭代版本用循环累乘依赖“维护一个中间状态并不断推进”。两者结果一样但思维路径完全不同。放到本题里递归版本是从树的定义出发直接翻译成代码迭代版本是手动维护一个容器把“系统帮我做的函数调用栈”显式地写出来。快速排序是另一个绝佳例子。快排的递归思路是选pivot分区然后递归排序左右两个区间。非递归快排就是把递归时由系统管理的“待排序区间”换成你自己的栈def quick_sort_iterative(arr): if len(arr) 1: return arr stack [(0, len(arr) - 1)] while stack: low, high stack.pop() if low high: continue pivot arr[(low high) // 2] i, j low, high while i j: while arr[i] pivot: i 1 while arr[j] pivot: j - 1 if i j: arr[i], arr[j] arr[j], arr[i] i 1 j - 1 if low j: stack.append((low, j)) if i high: stack.append((i, high)) return arr这里的核心思路和二叉树递归改迭代一模一样把隐式的函数调用栈换成显式的数据结构栈。理解了这一点不止单值二叉树任何“递归遍历树”的题目都能用同一套模板改成迭代版。5.4 什么场景该选递归什么场景该选迭代根据我个人的经验可以按下面这张表快速决策场景递归迭代代码简洁度高尤其树形结构低需要手动维护容器可读性接近问题定义接近执行细节栈溢出风险有深度受语言限制无容器在堆上调试难度函数调用轨迹直观容器状态需要自己理性能常数偏大偏小适合场景树、分治、回溯类问题深度不可控、性能敏感具体到单值判断树深度不确定时我直接写迭代深度可控、写Demo或面试讲解递归思想时我写递归。两者没有谁绝对取代谁能快速切换才是真本事。6. 实际刷题和面试中的常见失误与排查链路6.1 最容易犯的三个错第一个错误是忘判“存在性”。比如写if root.left.val ! root.val前没检查root.left是否为None。在Python里会直接报AttributeError: NoneType object has no attribute val。正确写法是先判断root.left存在再做值比较。第二个错误是目标值漂移。固定target的版本和双参数版本混着写一会儿用root.val做基准一会儿把node.val传下去但比较时又拿target去比导致逻辑混乱。第三个错误是混淆and和or。单值判断要求“所有条件同时满足”必须用and。如果把and写成or只要左子树或右子树有一个单值整棵树就被错误判定为单值这是逻辑层面的严重错误。6.2 一个真实排查过程为什么漏判了一个反例有一次我帮朋友看一段代码测试用例[1, null, 2]预期返回false实际却返回了true。他写的代码是这样的def is_unival_tree(root): if root is None: return True return is_unival_tree(root.left) and is_unival_tree(root.right)一眼就能看出问题递归函数里根本没有做任何值比较只判断了左右子树是否单值。对于[1, null, 2]来说左子树为空返回true右子树只有节点2也返回true所以整棵返回true。但更有意思的是为什么他之前的测试用例通过了因为他之前跑的树是[1, 1, 1]这种全等树全等树左右子树都单值即使漏掉值比较也返回true。他之所以没发现是测试用例只覆盖了“正例”没有覆盖“反例”。这次排查给我的启发是测试单值判断必须同时准备一个“整棵树全等但子树不全等”的用例比如[1, 1, 2]。它能立刻暴露你漏掉根节点与孩子值比较的问题。6.3 调试技巧打印递归轨迹和构造最小反例递归出问题时我习惯在函数入口加一行打印用缩进表示递归深度def dfs(node, depth0): if node is None: print( * depth None - True) return True print( * depth fvisit {node.val}) print( * depth fleft{node.left.val if node.left else None}, right{node.right.val if node.right else None}) ...跑[1, null, 2]时输出会清楚显示根节点1访问后直接进入右子树节点2根节点和右孩子的比较结果一目了然。调试另一个技巧是构造最小反例。单值二叉树的最小反例就是两个节点的树[1, 2]。如果这个用例不过说明递归逻辑有问题没必要先用复杂树去试。6.4 面试中怎么答才能加分这题虽然简单但面试官经常在follow-up里加东西。常见的追问包括“递归的空间复杂度是多少” 要答O(h)h是树高。“能不能改成迭代” 要会写显式栈版本。“如果树特别深递归会发生什么” 要能说出栈溢出和递归深度限制。“能不能用更小的空间” 理论上Morris遍历可以把空间压到O(1)但它会临时修改树结构对单值判断这种需要反复比较值的场景收益不大面试里点一句即可。我最喜欢的回答套路是先给出递归版然后主动说明调用栈开销再补一个迭代版对比。这样既展示了代码能力又展示了工程意识。刷这道题踩过几次坑之后我慢慢养成了一个小习惯凡是写递归先把终止条件、当前层职责、子问题组合方式这三件事写进注释里再动手写代码。单值二叉树只是个开始后续的“相同的树”“对称二叉树”“路径总和”全都是同一个套路。如果你也想把这套递归思维打牢我建议你把这题和上面提到那几题放在一起刷你会发现它们共享同一副骨架。最后留个小技巧给递归函数加一个带深度的打印函数调试完再删掉那一行以后遇到任何树形递归你都能快速定位问题。