刷到代码随想录系列的 Day16我突然有种被打通任督二脉的感觉。这一天不是简单堆了三道二叉树题而是把二叉树最核心的三个能力点在同一个下午集中轰炸了一遍226 翻转二叉树练的是遍历顺序和递归的配合101 对称二叉树考的是递归函数如何设计入参、如何构建镜像比较的语义104 二叉树的最大深度则把递归的返回值传递和层序迭代的层计数拉到同一张桌子上对比。很多刷题的人到了二叉树就头晕因为在数组、链表上还能靠直觉硬算但树的题目每一步都要求你先想清楚结构关系、再动手写代码这个思维转换很多人没跨过去。这篇文章不是抄一遍题解而是把我自己刷这三道题时踩过的坑、绕过的弯、以及后来才悟明白的细节全部摊开。不管你是刚开始刷二叉树的新手还是准备面试想系统过一遍树的题型只要把这三道题吃透后续遇到路径总和、树的直径、最近公共祖先这类进阶题你都会发现底层的“递归三要素”和“遍历顺序决定权”是同一套东西。1. 三道题放在一起的底层逻辑1.1 考察的知识点高度重合很多人把这三道题当作三个孤立的任务去刷刷一道忘一道这是最大的误区。你仔细看它们本质上都是“二叉树遍历顺序”的变种翻转二叉树的本质是在每个节点上执行左右孩子交换这一“访问动作”而这个动作放在前序、后序都成立对称二叉树是要对两棵子树做镜像比较本质上是同步遍历两棵树只不过入参从一个节点变成了两个节点二叉树最大深度的递归解法本质上又是后序遍历的深度累加。所以我在刷完这三道题之后最大的感受是二叉树题目看起来千变万化但只要把“遍历顺序”和“对节点的访问时机”吃透很多题的框架是共享的。你甚至可以把这三道题的递归模板放在一起对比会发现相似度非常高差异只在抽出的那个“访问动作”上。这就是为什么代码随想录要把它们排在连续几天里目的就是让你在重复的训练中形成肌肉记忆。1.2 贯穿始终的主线思维递归三要素代码随想录反复强调递归三要素参数与返回值、终止条件、单层递归逻辑。这三道题每一道都能完美套用这个框架而且套着套着你就会发现递归不再玄学。翻转二叉树的递归三要素是返回值是根节点终止条件是 root 为空单层逻辑是交换 root 的左右孩子然后分别递归处理。对称二叉树的递归三要素是入参变成两个节点左子树的某个节点和右子树镜像位置的某个节点终止条件要处理两节点为空的各种组合单层逻辑是比较外侧一对和内侧一对子节点。二叉树最大深度的递归三要素是返回值是当前子树的高度终止条件是 nil 节点返回 0单层逻辑是取左右子树深度的较大者再加一。这三道题如果分别用三要素拆解写出来的代码结构几乎同源。你真正需要训练的是根据题目要求快速写出三要素的能力而不是背代码。这也是我在刷题后期才明白的面试官考递归题目真正想看的就是你有没有把问题拆成子问题的思维。1.3 学习顺序与精力分配建议三道题的难度排序建议先刷翻转二叉树再刷最大深度最后刷对称二叉树。为什么这么排因为翻转最简单它就是递归三要素在树上的第一个应用能帮你建立“当前节点做什么、然后交给递归做什么”的直觉。最大深度稍微进阶一点因为它的返回值要参与计算但思路仍然是一元递归只有一个搜索方向。对称二叉树是这三道里思维难度最高的因为递归函数的入参变成了两个节点而且要交叉比较很多人第一次接触会懵为什么需要比较 left.Left 和 right.Right按这个顺序刷你会感觉难度是逐级爬坡而不是陡增。反过来先刷对称二叉树大概率第一天就被劝退了。2. 226. 翻转二叉树递归序的第一次正面交锋2.1 题面理解与暴力思路题目描述很简单给定一棵二叉树把它完整镜像翻转也就是每个节点的左右子树都交换。很多人第一次看到这题觉得不需要递归——直接 BFS 遍历每个节点交换左右指针不就行了这个思路完全可行但面试官通常会追问一句“能不能用递归写”因为递归写法才是这题真正的考点。在写递归之前你得先想清楚一个关键问题这个题目到底在“遍历”的过程中做什么操作二叉树的遍历无非是前序、中序、后序三种区别在于对当前节点的处理时机。翻转二叉树的核心操作是把当前节点的左右指针交换那么你只需要决定先交换再递归还是先递归再交换两个都行但都只对特定遍历顺序成立这就为后面的坑埋下伏笔。2.2 递归实现先换还是先下钻先看先交换的版本也就是前序遍历func invertTree(root *TreeNode) *TreeNode { if root nil { return nil } root.Left, root.Right root.Right, root.Left invertTree(root.Left) invertTree(root.Right) return root }这段代码的逻辑非常干净当前节点先把自己的左右孩子交换掉然后递归去翻转左子树和右子树。你可能会疑惑交换之后递归调用传来的 root.Left 到底是原来的左子树还是右子树答案是原来的右子树因为先交换了嘛。但这不影响结果因为反正两棵子树都要翻转变换顺序无所谓。再看后序遍历的版本也就是先递归再交换func invertTree(root *TreeNode) *TreeNode { if root nil { return nil } left : invertTree(root.Left) right : invertTree(root.Right) root.Left right root.Right left return root }这个版本先把左右子树分别翻转好再把当前节点的左右指针指向翻转后的子树。两版结果完全一样。真正要命的是中序遍历版本很多人会踩坑我放在后面小节专门讲。注意以上两个版本都是正确的因为它们都满足“每个节点恰好被访问一次并交换一次”的原则。区别只在于交换动作发生在递归下潜之前还是回溯之后。2.3 层序迭代解法用队列做镜像翻转递归解法干净但面试官经常追问“递归会不会栈溢出你写一个迭代版本”。树高很大的时候比如一条链状树递归深度可能达到 O(n)要是树有几万层程序直接栈溢出崩溃。这时候层序迭代就派上用场了func invertTree(root *TreeNode) *TreeNode { if root nil { return nil } queue : []*TreeNode{root} for len(queue) 0 { size : len(queue) for i : 0; i size; i { node : queue[0] queue queue[1:] node.Left, node.Right node.Right, node.Left if node.Left ! nil { queue append(queue, node.Left) } if node.Right ! nil { queue append(queue, node.Right) } } } return root }这里有个细节值得注意层序解法里交换动作是在出队时做的而且交换后入队的顺序其实已经不影响了——因为两棵子树都要处理。初学者容易纠结“先入左还是先入右”对这题真的无所谓你只要保证当前节点的两个孩子被交换过就行。但换成层序求其他结果时入队顺序就可能影响结果比如后面要讲的对称二叉树。2.4 易错点与实测细节翻转二叉树里最经典的一个坑就是中序遍历。很多人会写出这样的代码func invertTree(root *TreeNode) *TreeNode { if root nil { return nil } invertTree(root.Left) // 递归左子树 root.Left, root.Right root.Right, root.Left // 交换 invertTree(root.Left) // 递归“左子树” return root }看起来好像没问题先翻左交换再翻新的左即原来的右。但你仔细模拟就会发现这个写法会让部分节点被重复翻转。假设一棵只有三个节点的树根节点 1左孩子 2右孩子 3。中序写法先递归左子树翻转以 2 为根的子树然后交换 2 和 3此时根节点的左孩子变成了 3右孩子变成了 2再递归左子树也就是翻转以 3 为根的子树。结果是根节点的左子树被翻了两次右子树一次没翻整个结果的镜像关系完全错乱。所以我的建议是如果代码模板选用了中序遍历直接把交换去掉改成“连环赋值”的写法也能达到翻转效果但那样更难理解。翻转二叉树的正确打开方式就是前序或后序中序版本直接放弃不要为了一时逞能写一个容易出错的版本。还有一个低级的坑递归函数最后忘记返回 root。翻转操作是原地修改指针但调用方需要拿到根节点不返回 root 整个函数就白写了。这种低级错误在面试高压场景下很容易出现我建议你刷完一道题就把返回值习惯性写上。3. 101. 对称二叉树递归函数的语义设计3.1 对称的本质两棵子树互为镜像先理解什么叫做一棵二叉树对称。从根节点往下看不是左右孩子相等就叫对称而是左子树的左孩子要对应右子树的右孩子左子树的右孩子要对应右子树的左孩子。整个比较关系是交叉的、镜像的。换句话说你不能只写一个递归函数去看 root.Left 和 root.Right 是否相等因为这一步只是第一层判断。真正需要的是递归比较左子树的左孩子与右子树的右孩子、左子树的右孩子与右子树的左孩子。这个“交叉比较”是整道题的灵魂。所以这道题的难点在于你不应该把递归函数设计成“判断一棵树是否对称”而应该设计成“判断两棵树是否互为镜像”。这个语义上的转变是很多人卡住的根本原因。你是以一个节点的视角写递归还是以两个节点的视角写递归决定了整个代码的结构。3.2 递归解法双参数入参的设计这里我把递归逻辑完整展开。先看主函数和辅助函数func isSymmetric(root *TreeNode) bool { if root nil { return true } return compare(root.Left, root.Right) } func compare(left, right *TreeNode) bool { if left nil right nil { return true } if left nil || right nil { return false } if left.Val ! right.Val { return false } return compare(left.Left, right.Right) compare(left.Right, right.Left) }主函数很简单把 root 的左右子树交给 compare 函数。compare 函数接收两个节点它们的语义很明确“这两个节点在我们幻想的两棵树中处于镜像对称的位置”。如果 left 是原树中某个节点的左孩子那么 right 就是对应位置原树右孩子的节点。终止条件分三种情况场景leftright结果两个都为空nilniltrue一个为空nil非nil / 非nilnil值不等非nil非nilfalse只有两个都非空且值相等时才继续递归。单层递归的事情是当前两个节点值相等继续往下一层比较它们的孩子。因为镜像关系是交叉的所以下一次比较的是 left.Left 和 right.Right外侧以及 left.Right 和 right.Left内侧两者同时成立才算对称。我第一次写这道题时犯了用 compare(left.Left, right.Left) 去比较的错误结果发现左链和右链比了半天逻辑完全不对。所以要记住这个交叉规则镜像对称的递归比较永远是左对右、右对左。3.3 迭代解法用队列两两入队出队递归解法下潜到叶子节点就回溯但迭代解法需要你手动维护一个“待比较配对”的队列。核心思想是把应该互相比对的两个节点相邻放入队列每次出队两个节点进行比对。func isSymmetric(root *TreeNode) bool { if root nil { return true } queue : []*TreeNode{root.Left, root.Right} for len(queue) 0 { left : queue[0] right : queue[1] queue queue[2:] if left nil right nil { continue } if left nil || right nil || left.Val ! right.Val { return false } queue append(queue, left.Left, right.Right, left.Right, right.Left) } return true }这里有一个新手最容易踩的坑把 nil 节点直接跳过不放进队列。如果我这样写那 left 为 nil、right 非 nil 的情况就永远判断不到程序会错误地返回 true。所以队列里的 nil 元素不是垃圾数据而是用来占位和触发终止条件的哨兵。你在调试时如果发现对称判断漏判了先检查是不是 nil 没入队。另外一个细节是入队顺序。你看我的代码先放入 left.Left 和 right.Right再放入 left.Right 和 right.Left。这个顺序保证了每两个相邻的元素就是需要比较的镜像对。如果顺序写错比如先放 left.Left 再放 left.Right比较对象就被打乱了。这种 bug 特别隐蔽你只看队列里的元素会觉得每一个都差不多但实际上配对关系已经全乱了。3.4 边界条件与常见错误对称二叉树这道题的边界条件主要集中在根节点为空、单节点树、左右子树高度不同三种情况。根节点为空直接返回 true这是惯例不算什么坑。单节点树只有一个节点也返回 true。真正容易错的是左右子树高度不同的情况比如一棵树只有左子树没有右子树这时候 compare(root.Left, root.Right) 就会走到“一个为空一个非空”的分支返回 false逻辑没问题。还有一个很常见的错误是在递归函数里忘了 || 和 的短路顺序。比如有人会把三个 if 合并成if left nil || right nil || left.Val ! right.Val { return false }这段代码的问题是当 left 为 nil、right 非 nil 时走到 left.Val 会 panic因为 left 是空指针。所以必须先判断 left nil || right nil再判断值是否相等顺序不能乱。Go 里 || 的短路求值会保证 left.Val 在 left 非 nil 时才会被求值但如果你把 left.Val 的判断放在 leftnil 前面就直接 panic 了。这类空指针崩溃在面试白板代码中简直是送命题。4. 104. 二叉树的最大深度从递归到层序的思维切换4.1 深度概念与题面理解二叉树的最大深度定义是根节点到最远叶子节点的最长路径上的节点数。注意是节点数不是边的数量。所以空树的深度是 0只有一个根节点的树深度是 1根节点有一个左孩子的树深度是 2。这个“节点数”而不是“边数”的细节是很多人一开始容易忽略的尤其是后续做二叉树的直径、平衡二叉树判断时这个计数口径会直接影响公式推导。4.2 后序递归求解把问题拆给左右孩子先看递归解法的代码func maxDepth(root *TreeNode) int { if root nil { return 0 } leftDepth : maxDepth(root.Left) rightDepth : maxDepth(root.Right) if leftDepth rightDepth { return leftDepth 1 } return rightDepth 1 }这段代码完美的演示了什么是后序递归先递归左子树得到左子树深度再递归右子树得到右子树深度最后回到当前节点时取两者较大值加一作为当前子树的深度。为什么必须用后序因为父节点想知道自己的深度必须依赖子节点返回的深度结果这是典型的自底向上的信息收集过程。如果用前序你还没拿到孩子的深度就去算当前深度算出来的一定是错的。你可以在心里模拟一下递归调用栈叶子节点 nil 返回 0所以叶子节点那一层的 leftDepth 和 rightDepth 都是 0返回 1。再往上一层拿到左右子树各自的深度 1取大加一返回 2。以此类推一层一层把答案传回根节点。递归的关键就是相信子问题会正确返回结果你只需要处理“当前层1”这个关系。4.3 层序迭代求解BFS天然适合算深度迭代解法我强烈推荐直接用层序遍历因为 BFS 天然是一层一层扫的每次完整扫描完一层深度加一就行。代码也很直观func maxDepth(root *TreeNode) int { if root nil { return 0 } depth : 0 queue : []*TreeNode{root} for len(queue) 0 { size : len(queue) depth for i : 0; i size; i { node : queue[0] queue queue[1:] if node.Left ! nil { queue append(queue, node.Left) } if node.Right ! nil { queue append(queue, node.Right) } } } return depth }这里必须注意一个细节为什么内层循环要用 size : len(queue) 固定长度而不是直接 for len(queue) 0 一直弹因为一次外循环恰恰对应“当前这一层”的所有节点如果你不固定 size就会把下一层的节点也一起弹出深度计数就不准了。这个 size 固定的技巧在层序遍历相关题目中非常常见比如求每层平均值、找每层最大值都是基于这个模板改的。我建议把层序迭代版本练到可以盲写因为它的变体在二叉树题目里出现频率极高。你甚至可以把它当成一个标准模板背下来遇到求深度、求层数、按层输出的题目直接套。4.4 扩展题N叉树最大深度与最小深度的坑把最大深度从二叉树扩展到 N 叉树思路完全一样只是从递归两个子节点改成遍历所有孩子节点。Go 代码大概长这样func maxDepth(root *Node) int { if root nil { return 0 } max : 0 for _, child : range root.Children { depth : maxDepth(child) if depth max { max depth } } return max 1 }这个扩展很简单真正的坑是“最小深度”。很多人觉得最大深度的递归模板把 max 换成 min 不就行了大错特错。二叉树的最小深度是指根节点到最近叶子节点的最短路径上的节点数这里的重点在“叶子节点”。如果一棵树只有左子树没有右子树直接用 min(leftDepth, rightDepth)1 会在某个没有右孩子的非叶子节点上错误地返回 1但事实上这个节点不是叶子节点真正的最近叶子距离是 2。正确做法是要单独判断如果左子树为空就只递归右子树如果右子树为空就只递归左子树两者都为空才返回 1。很多面试题就是在最大深度的基础上加上这个弯子来考察你有没有真正理解“叶子节点”的定义。4.5 三者对比什么时候用递归什么时候用迭代这三道题刷完以后你应该形成自己的判断标准。我列一个简单的对照表判断维度递归解法迭代解法代码可读性高接近数学归纳法低需要维护队列/栈空间复杂度O(H)H为树高O(W)W为最大层宽最坏空间链状树 O(n)满二叉树最底层 O(n)栈溢出风险树很深时存在不存在适用场景子问题结构清晰的题目层序处理、深度计数我的个人习惯是如果题目问的答案是整棵树的某种聚合值深度、节点数、直径优先用递归写因为思路最清晰如果面试官特别追问性能或者题目要求按层输出、层序遍历那层序迭代就是标准答案。两道题都能写是二叉树进阶的基本功。5. 实战复盘刷完这三道题必须想明白的几件事5.1 递归终止条件的“最小问题”验证法我刷题时养成了一个习惯递归函数写完后先用最小问题验证终止条件。什么叫最小问题就是一棵空树、一个节点的树、两个节点的树。分别代入递归函数看会不会出现空指针、死循环或者逻辑错误。以对称二叉树为例最小问题验证法就是拿一棵只有左孩子没有右孩子的树去跑 compare 函数。遍历到第二个节点时left 是非 nil 的叶子节点right 是 nil这时候必须命中终止条件返回 false而不是继续递归访问 left.Left 导致 panic。如果递归函数里先判断值相等还是先判断 nil 的顺序错了这个最小问题立刻暴露。三个条件“left 和 right 都为空、只有一个为空、值不相等”的顺序就是递归函数的安全边界。5.2 遍历顺序选择的黄金法则我在刷完这几道题后总结了一个简单的法则如果当前节点的处理结果依赖于左右子树返回的信息用后序如果当前节点的处理动作发生在递归下潜之前并且不需要子树的信息用前序中序在二叉树问题中主要用于 BST 相关中序有序性日常翻转、求深度这类题目里中序往往不是最优选甚至像翻转二叉树那样直接出错。举个例子你就明白了求深度必须先把左右子树挖到底拿到结果才能算当前层深度所以是后序。翻转二叉树直接交换左右指针把交换动作放在递归下潜前或回溯后都行但不能放在中序位置。对称二叉树的 compare 其实也是后序的变体它先比对当前两个节点再递归下去回来后把两边的结果做 合并。5.3 调试二叉树代码的实用技巧二叉树代码出 bug 的时候靠 print 打日志往往手忙脚乱我建议你准备一个把树转成字符串的工具函数这在本地调试时非常管用func printTree(root *TreeNode, level int) { if root nil { return } fmt.Printf(%*s%d\n, level*2, , root.Val) printTree(root.Left, level1) printTree(root.Right, level1) }比如翻转二叉树代码写完你可以先打印原始树输出翻转后的树用缩进层次直观地看出左右子树是否真的交换了对称二叉树的递归比较函数出问题时在 compare 函数开头打印 left 和 right 的值就能看出递归顺序到底是交叉比较还是同侧比较。还有一个技巧是从小数据测起别一上来就构造一棵 10 层的大树。先用最简单的 3 节点树、5 节点树手推一遍递归顺序确认无误再测复杂用例。很多递归逻辑的问题在 3 节点树上就能暴露。5.4 复杂度分析必须动手算很多人刷题只看代码对错不分析复杂度面试时被追问就卡壳。这三道题的递归解法时间复杂度都是 O(n)n 是节点数因为每个节点恰好被访问一次。空间复杂度就不是很多人口中轻飘飘的 O(1) 了递归解法最坏情况下要 O(H)其中 H 是树高当树退化成一条链时H 等于 n空间复杂度变成 O(n)。这个点经常被忽略部分资料甚至误导说递归空间是 O(1)。迭代解法用队列存储空间复杂度取决于最大层宽满二叉树的最底层节点数大约是 n/2所以最坏也是 O(n)。我建议你养成一个习惯每写完一道树题在注释里写上时间复杂度和空间复杂度以及最坏情况何时发生。这不仅能帮你应付面试追问更重要的是逼自己想清楚算法到底消耗了多少资源。三道题刷完最大的收获不是会写三道题而是你终于敢面对象限更广的二叉树题目了。后续的路径总和、二叉树最近公共祖先、二叉搜索树的各种操作本质上都逃不出递归三要素、遍历顺序、空间复杂度这三个核心词的组合。真正把这几道题吃透再往后刷到树的进阶题时你会明显发现自己不再对着题目发呆而是能直接开始拆解递归逻辑了。
刷到代码随想录系列的 Day16我突然有种被打通任督二脉的感觉。这一天不是简单堆了三道二叉树题而是把二叉树最核心的三个能力点在同一个下午集中轰炸了一遍226 翻转二叉树练的是遍历顺序和递归的配合101 对称二叉树考的是递归函数如何设计入参、如何构建镜像比较的语义104 二叉树的最大深度则把递归的返回值传递和层序迭代的层计数拉到同一张桌子上对比。很多刷题的人到了二叉树就头晕因为在数组、链表上还能靠直觉硬算但树的题目每一步都要求你先想清楚结构关系、再动手写代码这个思维转换很多人没跨过去。这篇文章不是抄一遍题解而是把我自己刷这三道题时踩过的坑、绕过的弯、以及后来才悟明白的细节全部摊开。不管你是刚开始刷二叉树的新手还是准备面试想系统过一遍树的题型只要把这三道题吃透后续遇到路径总和、树的直径、最近公共祖先这类进阶题你都会发现底层的“递归三要素”和“遍历顺序决定权”是同一套东西。1. 三道题放在一起的底层逻辑1.1 考察的知识点高度重合很多人把这三道题当作三个孤立的任务去刷刷一道忘一道这是最大的误区。你仔细看它们本质上都是“二叉树遍历顺序”的变种翻转二叉树的本质是在每个节点上执行左右孩子交换这一“访问动作”而这个动作放在前序、后序都成立对称二叉树是要对两棵子树做镜像比较本质上是同步遍历两棵树只不过入参从一个节点变成了两个节点二叉树最大深度的递归解法本质上又是后序遍历的深度累加。所以我在刷完这三道题之后最大的感受是二叉树题目看起来千变万化但只要把“遍历顺序”和“对节点的访问时机”吃透很多题的框架是共享的。你甚至可以把这三道题的递归模板放在一起对比会发现相似度非常高差异只在抽出的那个“访问动作”上。这就是为什么代码随想录要把它们排在连续几天里目的就是让你在重复的训练中形成肌肉记忆。1.2 贯穿始终的主线思维递归三要素代码随想录反复强调递归三要素参数与返回值、终止条件、单层递归逻辑。这三道题每一道都能完美套用这个框架而且套着套着你就会发现递归不再玄学。翻转二叉树的递归三要素是返回值是根节点终止条件是 root 为空单层逻辑是交换 root 的左右孩子然后分别递归处理。对称二叉树的递归三要素是入参变成两个节点左子树的某个节点和右子树镜像位置的某个节点终止条件要处理两节点为空的各种组合单层逻辑是比较外侧一对和内侧一对子节点。二叉树最大深度的递归三要素是返回值是当前子树的高度终止条件是 nil 节点返回 0单层逻辑是取左右子树深度的较大者再加一。这三道题如果分别用三要素拆解写出来的代码结构几乎同源。你真正需要训练的是根据题目要求快速写出三要素的能力而不是背代码。这也是我在刷题后期才明白的面试官考递归题目真正想看的就是你有没有把问题拆成子问题的思维。1.3 学习顺序与精力分配建议三道题的难度排序建议先刷翻转二叉树再刷最大深度最后刷对称二叉树。为什么这么排因为翻转最简单它就是递归三要素在树上的第一个应用能帮你建立“当前节点做什么、然后交给递归做什么”的直觉。最大深度稍微进阶一点因为它的返回值要参与计算但思路仍然是一元递归只有一个搜索方向。对称二叉树是这三道里思维难度最高的因为递归函数的入参变成了两个节点而且要交叉比较很多人第一次接触会懵为什么需要比较 left.Left 和 right.Right按这个顺序刷你会感觉难度是逐级爬坡而不是陡增。反过来先刷对称二叉树大概率第一天就被劝退了。2. 226. 翻转二叉树递归序的第一次正面交锋2.1 题面理解与暴力思路题目描述很简单给定一棵二叉树把它完整镜像翻转也就是每个节点的左右子树都交换。很多人第一次看到这题觉得不需要递归——直接 BFS 遍历每个节点交换左右指针不就行了这个思路完全可行但面试官通常会追问一句“能不能用递归写”因为递归写法才是这题真正的考点。在写递归之前你得先想清楚一个关键问题这个题目到底在“遍历”的过程中做什么操作二叉树的遍历无非是前序、中序、后序三种区别在于对当前节点的处理时机。翻转二叉树的核心操作是把当前节点的左右指针交换那么你只需要决定先交换再递归还是先递归再交换两个都行但都只对特定遍历顺序成立这就为后面的坑埋下伏笔。2.2 递归实现先换还是先下钻先看先交换的版本也就是前序遍历func invertTree(root *TreeNode) *TreeNode { if root nil { return nil } root.Left, root.Right root.Right, root.Left invertTree(root.Left) invertTree(root.Right) return root }这段代码的逻辑非常干净当前节点先把自己的左右孩子交换掉然后递归去翻转左子树和右子树。你可能会疑惑交换之后递归调用传来的 root.Left 到底是原来的左子树还是右子树答案是原来的右子树因为先交换了嘛。但这不影响结果因为反正两棵子树都要翻转变换顺序无所谓。再看后序遍历的版本也就是先递归再交换func invertTree(root *TreeNode) *TreeNode { if root nil { return nil } left : invertTree(root.Left) right : invertTree(root.Right) root.Left right root.Right left return root }这个版本先把左右子树分别翻转好再把当前节点的左右指针指向翻转后的子树。两版结果完全一样。真正要命的是中序遍历版本很多人会踩坑我放在后面小节专门讲。注意以上两个版本都是正确的因为它们都满足“每个节点恰好被访问一次并交换一次”的原则。区别只在于交换动作发生在递归下潜之前还是回溯之后。2.3 层序迭代解法用队列做镜像翻转递归解法干净但面试官经常追问“递归会不会栈溢出你写一个迭代版本”。树高很大的时候比如一条链状树递归深度可能达到 O(n)要是树有几万层程序直接栈溢出崩溃。这时候层序迭代就派上用场了func invertTree(root *TreeNode) *TreeNode { if root nil { return nil } queue : []*TreeNode{root} for len(queue) 0 { size : len(queue) for i : 0; i size; i { node : queue[0] queue queue[1:] node.Left, node.Right node.Right, node.Left if node.Left ! nil { queue append(queue, node.Left) } if node.Right ! nil { queue append(queue, node.Right) } } } return root }这里有个细节值得注意层序解法里交换动作是在出队时做的而且交换后入队的顺序其实已经不影响了——因为两棵子树都要处理。初学者容易纠结“先入左还是先入右”对这题真的无所谓你只要保证当前节点的两个孩子被交换过就行。但换成层序求其他结果时入队顺序就可能影响结果比如后面要讲的对称二叉树。2.4 易错点与实测细节翻转二叉树里最经典的一个坑就是中序遍历。很多人会写出这样的代码func invertTree(root *TreeNode) *TreeNode { if root nil { return nil } invertTree(root.Left) // 递归左子树 root.Left, root.Right root.Right, root.Left // 交换 invertTree(root.Left) // 递归“左子树” return root }看起来好像没问题先翻左交换再翻新的左即原来的右。但你仔细模拟就会发现这个写法会让部分节点被重复翻转。假设一棵只有三个节点的树根节点 1左孩子 2右孩子 3。中序写法先递归左子树翻转以 2 为根的子树然后交换 2 和 3此时根节点的左孩子变成了 3右孩子变成了 2再递归左子树也就是翻转以 3 为根的子树。结果是根节点的左子树被翻了两次右子树一次没翻整个结果的镜像关系完全错乱。所以我的建议是如果代码模板选用了中序遍历直接把交换去掉改成“连环赋值”的写法也能达到翻转效果但那样更难理解。翻转二叉树的正确打开方式就是前序或后序中序版本直接放弃不要为了一时逞能写一个容易出错的版本。还有一个低级的坑递归函数最后忘记返回 root。翻转操作是原地修改指针但调用方需要拿到根节点不返回 root 整个函数就白写了。这种低级错误在面试高压场景下很容易出现我建议你刷完一道题就把返回值习惯性写上。3. 101. 对称二叉树递归函数的语义设计3.1 对称的本质两棵子树互为镜像先理解什么叫做一棵二叉树对称。从根节点往下看不是左右孩子相等就叫对称而是左子树的左孩子要对应右子树的右孩子左子树的右孩子要对应右子树的左孩子。整个比较关系是交叉的、镜像的。换句话说你不能只写一个递归函数去看 root.Left 和 root.Right 是否相等因为这一步只是第一层判断。真正需要的是递归比较左子树的左孩子与右子树的右孩子、左子树的右孩子与右子树的左孩子。这个“交叉比较”是整道题的灵魂。所以这道题的难点在于你不应该把递归函数设计成“判断一棵树是否对称”而应该设计成“判断两棵树是否互为镜像”。这个语义上的转变是很多人卡住的根本原因。你是以一个节点的视角写递归还是以两个节点的视角写递归决定了整个代码的结构。3.2 递归解法双参数入参的设计这里我把递归逻辑完整展开。先看主函数和辅助函数func isSymmetric(root *TreeNode) bool { if root nil { return true } return compare(root.Left, root.Right) } func compare(left, right *TreeNode) bool { if left nil right nil { return true } if left nil || right nil { return false } if left.Val ! right.Val { return false } return compare(left.Left, right.Right) compare(left.Right, right.Left) }主函数很简单把 root 的左右子树交给 compare 函数。compare 函数接收两个节点它们的语义很明确“这两个节点在我们幻想的两棵树中处于镜像对称的位置”。如果 left 是原树中某个节点的左孩子那么 right 就是对应位置原树右孩子的节点。终止条件分三种情况场景leftright结果两个都为空nilniltrue一个为空nil非nil / 非nilnil值不等非nil非nilfalse只有两个都非空且值相等时才继续递归。单层递归的事情是当前两个节点值相等继续往下一层比较它们的孩子。因为镜像关系是交叉的所以下一次比较的是 left.Left 和 right.Right外侧以及 left.Right 和 right.Left内侧两者同时成立才算对称。我第一次写这道题时犯了用 compare(left.Left, right.Left) 去比较的错误结果发现左链和右链比了半天逻辑完全不对。所以要记住这个交叉规则镜像对称的递归比较永远是左对右、右对左。3.3 迭代解法用队列两两入队出队递归解法下潜到叶子节点就回溯但迭代解法需要你手动维护一个“待比较配对”的队列。核心思想是把应该互相比对的两个节点相邻放入队列每次出队两个节点进行比对。func isSymmetric(root *TreeNode) bool { if root nil { return true } queue : []*TreeNode{root.Left, root.Right} for len(queue) 0 { left : queue[0] right : queue[1] queue queue[2:] if left nil right nil { continue } if left nil || right nil || left.Val ! right.Val { return false } queue append(queue, left.Left, right.Right, left.Right, right.Left) } return true }这里有一个新手最容易踩的坑把 nil 节点直接跳过不放进队列。如果我这样写那 left 为 nil、right 非 nil 的情况就永远判断不到程序会错误地返回 true。所以队列里的 nil 元素不是垃圾数据而是用来占位和触发终止条件的哨兵。你在调试时如果发现对称判断漏判了先检查是不是 nil 没入队。另外一个细节是入队顺序。你看我的代码先放入 left.Left 和 right.Right再放入 left.Right 和 right.Left。这个顺序保证了每两个相邻的元素就是需要比较的镜像对。如果顺序写错比如先放 left.Left 再放 left.Right比较对象就被打乱了。这种 bug 特别隐蔽你只看队列里的元素会觉得每一个都差不多但实际上配对关系已经全乱了。3.4 边界条件与常见错误对称二叉树这道题的边界条件主要集中在根节点为空、单节点树、左右子树高度不同三种情况。根节点为空直接返回 true这是惯例不算什么坑。单节点树只有一个节点也返回 true。真正容易错的是左右子树高度不同的情况比如一棵树只有左子树没有右子树这时候 compare(root.Left, root.Right) 就会走到“一个为空一个非空”的分支返回 false逻辑没问题。还有一个很常见的错误是在递归函数里忘了 || 和 的短路顺序。比如有人会把三个 if 合并成if left nil || right nil || left.Val ! right.Val { return false }这段代码的问题是当 left 为 nil、right 非 nil 时走到 left.Val 会 panic因为 left 是空指针。所以必须先判断 left nil || right nil再判断值是否相等顺序不能乱。Go 里 || 的短路求值会保证 left.Val 在 left 非 nil 时才会被求值但如果你把 left.Val 的判断放在 leftnil 前面就直接 panic 了。这类空指针崩溃在面试白板代码中简直是送命题。4. 104. 二叉树的最大深度从递归到层序的思维切换4.1 深度概念与题面理解二叉树的最大深度定义是根节点到最远叶子节点的最长路径上的节点数。注意是节点数不是边的数量。所以空树的深度是 0只有一个根节点的树深度是 1根节点有一个左孩子的树深度是 2。这个“节点数”而不是“边数”的细节是很多人一开始容易忽略的尤其是后续做二叉树的直径、平衡二叉树判断时这个计数口径会直接影响公式推导。4.2 后序递归求解把问题拆给左右孩子先看递归解法的代码func maxDepth(root *TreeNode) int { if root nil { return 0 } leftDepth : maxDepth(root.Left) rightDepth : maxDepth(root.Right) if leftDepth rightDepth { return leftDepth 1 } return rightDepth 1 }这段代码完美的演示了什么是后序递归先递归左子树得到左子树深度再递归右子树得到右子树深度最后回到当前节点时取两者较大值加一作为当前子树的深度。为什么必须用后序因为父节点想知道自己的深度必须依赖子节点返回的深度结果这是典型的自底向上的信息收集过程。如果用前序你还没拿到孩子的深度就去算当前深度算出来的一定是错的。你可以在心里模拟一下递归调用栈叶子节点 nil 返回 0所以叶子节点那一层的 leftDepth 和 rightDepth 都是 0返回 1。再往上一层拿到左右子树各自的深度 1取大加一返回 2。以此类推一层一层把答案传回根节点。递归的关键就是相信子问题会正确返回结果你只需要处理“当前层1”这个关系。4.3 层序迭代求解BFS天然适合算深度迭代解法我强烈推荐直接用层序遍历因为 BFS 天然是一层一层扫的每次完整扫描完一层深度加一就行。代码也很直观func maxDepth(root *TreeNode) int { if root nil { return 0 } depth : 0 queue : []*TreeNode{root} for len(queue) 0 { size : len(queue) depth for i : 0; i size; i { node : queue[0] queue queue[1:] if node.Left ! nil { queue append(queue, node.Left) } if node.Right ! nil { queue append(queue, node.Right) } } } return depth }这里必须注意一个细节为什么内层循环要用 size : len(queue) 固定长度而不是直接 for len(queue) 0 一直弹因为一次外循环恰恰对应“当前这一层”的所有节点如果你不固定 size就会把下一层的节点也一起弹出深度计数就不准了。这个 size 固定的技巧在层序遍历相关题目中非常常见比如求每层平均值、找每层最大值都是基于这个模板改的。我建议把层序迭代版本练到可以盲写因为它的变体在二叉树题目里出现频率极高。你甚至可以把它当成一个标准模板背下来遇到求深度、求层数、按层输出的题目直接套。4.4 扩展题N叉树最大深度与最小深度的坑把最大深度从二叉树扩展到 N 叉树思路完全一样只是从递归两个子节点改成遍历所有孩子节点。Go 代码大概长这样func maxDepth(root *Node) int { if root nil { return 0 } max : 0 for _, child : range root.Children { depth : maxDepth(child) if depth max { max depth } } return max 1 }这个扩展很简单真正的坑是“最小深度”。很多人觉得最大深度的递归模板把 max 换成 min 不就行了大错特错。二叉树的最小深度是指根节点到最近叶子节点的最短路径上的节点数这里的重点在“叶子节点”。如果一棵树只有左子树没有右子树直接用 min(leftDepth, rightDepth)1 会在某个没有右孩子的非叶子节点上错误地返回 1但事实上这个节点不是叶子节点真正的最近叶子距离是 2。正确做法是要单独判断如果左子树为空就只递归右子树如果右子树为空就只递归左子树两者都为空才返回 1。很多面试题就是在最大深度的基础上加上这个弯子来考察你有没有真正理解“叶子节点”的定义。4.5 三者对比什么时候用递归什么时候用迭代这三道题刷完以后你应该形成自己的判断标准。我列一个简单的对照表判断维度递归解法迭代解法代码可读性高接近数学归纳法低需要维护队列/栈空间复杂度O(H)H为树高O(W)W为最大层宽最坏空间链状树 O(n)满二叉树最底层 O(n)栈溢出风险树很深时存在不存在适用场景子问题结构清晰的题目层序处理、深度计数我的个人习惯是如果题目问的答案是整棵树的某种聚合值深度、节点数、直径优先用递归写因为思路最清晰如果面试官特别追问性能或者题目要求按层输出、层序遍历那层序迭代就是标准答案。两道题都能写是二叉树进阶的基本功。5. 实战复盘刷完这三道题必须想明白的几件事5.1 递归终止条件的“最小问题”验证法我刷题时养成了一个习惯递归函数写完后先用最小问题验证终止条件。什么叫最小问题就是一棵空树、一个节点的树、两个节点的树。分别代入递归函数看会不会出现空指针、死循环或者逻辑错误。以对称二叉树为例最小问题验证法就是拿一棵只有左孩子没有右孩子的树去跑 compare 函数。遍历到第二个节点时left 是非 nil 的叶子节点right 是 nil这时候必须命中终止条件返回 false而不是继续递归访问 left.Left 导致 panic。如果递归函数里先判断值相等还是先判断 nil 的顺序错了这个最小问题立刻暴露。三个条件“left 和 right 都为空、只有一个为空、值不相等”的顺序就是递归函数的安全边界。5.2 遍历顺序选择的黄金法则我在刷完这几道题后总结了一个简单的法则如果当前节点的处理结果依赖于左右子树返回的信息用后序如果当前节点的处理动作发生在递归下潜之前并且不需要子树的信息用前序中序在二叉树问题中主要用于 BST 相关中序有序性日常翻转、求深度这类题目里中序往往不是最优选甚至像翻转二叉树那样直接出错。举个例子你就明白了求深度必须先把左右子树挖到底拿到结果才能算当前层深度所以是后序。翻转二叉树直接交换左右指针把交换动作放在递归下潜前或回溯后都行但不能放在中序位置。对称二叉树的 compare 其实也是后序的变体它先比对当前两个节点再递归下去回来后把两边的结果做 合并。5.3 调试二叉树代码的实用技巧二叉树代码出 bug 的时候靠 print 打日志往往手忙脚乱我建议你准备一个把树转成字符串的工具函数这在本地调试时非常管用func printTree(root *TreeNode, level int) { if root nil { return } fmt.Printf(%*s%d\n, level*2, , root.Val) printTree(root.Left, level1) printTree(root.Right, level1) }比如翻转二叉树代码写完你可以先打印原始树输出翻转后的树用缩进层次直观地看出左右子树是否真的交换了对称二叉树的递归比较函数出问题时在 compare 函数开头打印 left 和 right 的值就能看出递归顺序到底是交叉比较还是同侧比较。还有一个技巧是从小数据测起别一上来就构造一棵 10 层的大树。先用最简单的 3 节点树、5 节点树手推一遍递归顺序确认无误再测复杂用例。很多递归逻辑的问题在 3 节点树上就能暴露。5.4 复杂度分析必须动手算很多人刷题只看代码对错不分析复杂度面试时被追问就卡壳。这三道题的递归解法时间复杂度都是 O(n)n 是节点数因为每个节点恰好被访问一次。空间复杂度就不是很多人口中轻飘飘的 O(1) 了递归解法最坏情况下要 O(H)其中 H 是树高当树退化成一条链时H 等于 n空间复杂度变成 O(n)。这个点经常被忽略部分资料甚至误导说递归空间是 O(1)。迭代解法用队列存储空间复杂度取决于最大层宽满二叉树的最底层节点数大约是 n/2所以最坏也是 O(n)。我建议你养成一个习惯每写完一道树题在注释里写上时间复杂度和空间复杂度以及最坏情况何时发生。这不仅能帮你应付面试追问更重要的是逼自己想清楚算法到底消耗了多少资源。三道题刷完最大的收获不是会写三道题而是你终于敢面对象限更广的二叉树题目了。后续的路径总和、二叉树最近公共祖先、二叉搜索树的各种操作本质上都逃不出递归三要素、遍历顺序、空间复杂度这三个核心词的组合。真正把这几道题吃透再往后刷到树的进阶题时你会明显发现自己不再对着题目发呆而是能直接开始拆解递归逻辑了。
