★ FEATURED ARTICLE 1. 为什么二叉树本身就是一座完整的算法练习场干了这么多年开发我越来越觉得二叉树这类题目是被低估的。很多人一听到树就下意识觉得离业务很远但实际上无论是前端操作目录树、后端解析表达式、还是做权限菜单的层级校验底层全在跟树打交道。而二叉树作为树的收敛形态几乎浓缩了算法面试里最核心的一批思维模型递归、分治、回溯、栈、队列、动态规划、序列化、最近公共祖先……可以说把二叉树这一块吃透你对算法的整体理解会上一个台阶。这篇文章我会把二叉树相关的算法做一个相对系统的梳理从遍历框架讲到高频题型的识别方法再到我自己刷题过程中的避坑清单。内容会偏实战每一步都会给代码和解释不讲虚的。适合正在准备笔试面试的同学也适合写过一些树但总觉得会写题、不会变通的开发者。我会尽量讲清楚每个思路的来源——为什么用这个数据结构、为什么递归出口要这样写、为什么有时候返回值不是节点本身而是个数字这些理解了题目怎么变你都不慌。先说个总的认识二叉树算法虽然题型多但底层其实就那么二十几种套路。树的前序、中序、后序遍历是骨架所有题目几乎都建立在遍历之上层序遍历是另一条线专门解决按层处理的问题再往上是围绕节点关系的题型比如最近公共祖先、路径求和、树形动态规划、序列化重建。你把这些模块拆开练比漫无目的地一天刷十题要有效得多。2. 遍历是几乎所有二叉树题的地基递归框架怎么搭2.1 前序、中序、后序的递归框架为什么长一样先放一个我自己的总结二叉树的递归遍历永远只需要关心三件事——当前节点做什么、左子树做什么、右子树做什么。至于什么时候做决定了你是前序、中序还是后序。def traverse(root): if root is None: return # 前序位置刚进入节点时 traverse(root.left) # 中序位置左子树遍历完回到当前节点时 traverse(root.right) # 后序位置右子树遍历完即将离开节点时这段代码就是一个完整的三种遍历框架。前序就是先访问当前节点再递归左右中序就是先左再当前再右后序就是先左右再当前。从执行角度看每个节点其实会经过三个位置三次你在不同位置写逻辑输出结果就不同。这里我想强调一个很多人没意识到的点递归框架里的前中后并不是树的天然属性而是你选择处理时机的策略。树的形状没变变的是你在递归回溯路径上的哪个时刻做操作。理解这一点之后很多题目你就能想明白为什么要用后序——因为后序意味着你已经完整掌握了左子树和右子树的信息可以对它们做汇总。2.2 前序遍历的两个典型应用数组重建与节点复制前序遍历最常见的两个应用场景是二叉树的序列化和复制。序列化时按根-左-右顺序输出反序列化时也是按同样顺序重建顺序一致才能保证唯一还原。复制树同理先复制当前节点再递归复制左右子树这样新树的父子关系才不会错乱。def serialize(root): if root is None: return X left serialize(root.left) right serialize(root.right) return f{root.val},{left},{right}注意上面这个写法其实是后序但序列化的核心逻辑并不强制前中后关键在于空节点要显式标记。我在这里用后序只是为了演示不同遍历顺序可以完成同一件事只要保持编码时使用什么顺序解码时就按什么顺序。实际刷题时序列化用前序更直观反序列化时用一个全局指针按前序依次重建就行下面第五节我会展开讲。2.3 中序遍历与二叉搜索树顺序性带来的红利中序遍历的特殊价值在于它能得到一个有序序列。这个性质决定了二叉搜索树BST的大部分题目都围绕中序展开验证BST合法性、找第K小元素、中序转双向链表、删除节点后调整结构。以验证BST为例最常见的错误想法是对每个节点判断左孩子小于自己、右孩子大于自己这个思路是错的因为BST要求的是左右子树整体范围约束不是只和直接孩子比较。正确做法是把合法区间作为参数传递下去def is_valid_bst(root, lowerNone, upperNone): if root is None: return True if lower is not None and root.val lower: return False if upper is not None and root.val upper: return False return (is_valid_bst(root.left, lower, root.val) and is_valid_bst(root.right, root.val, upper))为什么中序也能解因为中序遍历BST得到升序序列只要在遍历过程中记录前一个节点的值发现当前值比前一个值小或等于就说明不合法。两种解法本质是一个思路用BST的全局有序性约束节点的位置。我个人建议两个都掌握区间法适合理解范围传递的递归思想中序法适合代码简洁度要求高的场景。2.4 后序遍历自底向上汇聚信息的利器后序是我个人认为最能体现递归精髓的顺序。它的特点是先处理完整棵子树再回到当前节点做决策。很多需要子树信息才能决定当前节点状态的题都靠后序遍历解决。最典型的就是二叉树的最大深度。当然这道题用前序加全局变量也能做但后序更自然def max_depth(root): if root is None: return 0 left_depth max_depth(root.left) right_depth max_depth(root.right) return max(left_depth, right_depth) 1代码只有四行但它展示了一个极其重要的思维转变不要思考遍历过程要思考假设我已经知道左子树深度和右子树深度当前节点的答案是什么。这个思维模式就是树形动态规划的基础。后面讲路径和、最近公共祖先时你会反复看到它。3. 递归转迭代栈模拟与层序队列两条技术路线3.1 为什么面试官总爱追问能不能不用递归写递归代码简洁但有两个实际缺陷一是递归深度受调用栈限制处理一条退化链每个节点只有左孩子时深度为NN1000左右就可能爆栈二是递归版本隐藏了函数调用开销对性能敏感的场景不友好。所以面试和工程实践里迭代写法是绕不开的。但迭代写遍历最核心的技巧只有一个用栈模拟递归的调用栈显式控制节点的处理顺序。前序和中序可以统一出一套模板后序稍微特殊一点我后面会单独说。前序遍历的迭代写法def preorder(root): if root is None: return [] stack, result [root], [] while stack: node stack.pop() result.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return result注意压栈顺序是先右后左。为什么要倒着压因为栈是后进先出你想先处理左子树就必须让左子树最后进栈。这个细节我见过很多初学者踩坑代码写出来结果顺序完全错乱然后开始怀疑栈这个数据结构 —— 其实只是压栈顺序反了。中序迭代的写法def inorder(root): stack, result [], [] cur root while cur or stack: while cur: stack.append(cur) cur cur.left cur stack.pop() result.append(cur.val) cur cur.right return result中序的迭代思路是沿左链一路入栈弹栈访问后转向右子树。这个写法的核心是理解访问时机出栈的时候访问是因为栈里的节点已经完成了左子树的处理此时回到当前节点正好是中序位置。后序迭代有一个经典讨巧办法用前序的根-右-左顺序遍历然后反转结果得到左-右-根的后序。实现如下def postorder(root): if root is None: return [] stack, result [root], [] while stack: node stack.pop() result.append(node.val) if node.left: stack.append(node.left) if node.right: stack.append(node.right) return result[::-1]这个技巧在LeetCode上很好用但我建议你至少要知道另一种双栈法或前驱标记法的原理因为有些衍生题不能直接反转解决。反转适合纯粹的后序遍历输出而一旦需要边遍历边做状态收集反转思路就不够用了。3.2 层序遍历BFS的标准双循环套路层序遍历用的不是栈而是队列。它的特点是逐层处理天然适合求层级相关的答案二叉树最小深度、右侧视图、锯齿形遍历、同层节点连接等等。from collections import deque def level_order(root): if root is None: return [] queue deque([root]) result [] while queue: level_size len(queue) level_vals [] for _ in range(level_size): node queue.popleft() level_vals.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level_vals) return result这里的关键是level_size len(queue)这一行。因为进入循环时队列里恰好存着当前层的所有节点用这个长度控制内层循环就能把同一层的节点一次性取完。这也是BFS和DFS最大的不同DFS关注的是路径BFS关注的是层次。理解了这一点你就不会在写层序遍历时把queue的长度动态判断写错。层序框架的另一个优点是可以方便地在每层切换方向实现之字形遍历。你只需要在往result里追加level_vals前根据当前层数的奇偶决定是否反转列表。3.3 迭代遍历时的一个隐蔽坑节点重复入队/入栈我自己写迭代遍历时最常犯的错是让节点重复入队。比如层序遍历时如果忘记在pop后立刻检查子节点并入队下一次循环可能又把这个节点处理一遍。更隐蔽的情况是在连接右侧指针这类题目里如果队列清空条件写得不对结果就是死循环。解决这类问题没有花哨技巧最有效的办法是在代码里加注释标记每个节点的入队时机和出队时机。看起来有点笨但排查的时候非常高效。我甚至见过有人因为一个queue.append的位置写错debug了一个晚上结果只是把空的子节点也放进去了。4. 从经典题型里拆出真正值得记忆的模式4.1 最近公共祖先后序遍历与返回值的语义设计最近公共祖先LCA这道题几乎是大厂笔试的高频题。它叫祖先但解法却要用后序因为你要从底部向上找先探查左右子树里有没有目标节点再判断当前节点是不是公共祖先。def lowest_common_ancestor(root, p, q): if root is None or root p or root q: return root left lowest_common_ancestor(root.left, p, q) right lowest_common_ancestor(root.right, p, q) if left and right: return root return left if left else right很多人第一次看这段代码时觉得这太魔法了。它其实有个隐藏约束函数的返回值被设计为以root为根的子树中p或q的找到情况。如果一个节点同时从左子树和右子树都找到了目标说明它是LCA如果只从一个方向找到就把那个找到的节点向上传递如果两边都没有返回空。理解了这个返回值语义你就解锁了一整类题目判断一棵树是否是另一棵树的子树、计算树中距离等于K的节点值之和、以及各类自底向上传递信息的问题。我认为这才是这道题的真正价值——它不是一道孤立的题而是一种信息聚拢的模式。4.2 路径类问题从和等于目标值到最大路径和路径类问题是二叉树题目里最考验逻辑分类的一块。核心难点不在递归本身而在于路径的几何形状有的路径必须从根出发有的必须是直上直下的有的允许任意起止点。这些形状决定了一个递归函数的返回值到底应该是什么。最简单的根到叶子路径之和是最基础的一版。它要求每次往下走时把目标值减去当前节点值直到叶子节点检查是否减到零。这种减法的写法比带一个累计变量更不容易出错def has_path_sum(root, target_sum): if root is None: return False if root.left is None and root.right is None: return root.val target_sum return (has_path_sum(root.left, target_sum - root.val) or has_path_sum(root.right, target_sum - root.val))再进阶一层如果路径可以是任意起点到任意终点比如求二叉树中的最大路径和这时要引入路径贡献值的概念。每个节点向父节点能提供的最大贡献不是在当前节点结束的完整路径和而是单侧路径的最大值def max_path_sum(root): res float(-inf) def dfs(node): if node is None: return 0 left_gain max(dfs(node.left), 0) right_gain max(dfs(node.right), 0) current_sum node.val left_gain right_gain res max(res, current_sum) return node.val max(left_gain, right_gain) dfs(root) return res这段代码用了一个嵌套函数和一个外部变量res。注意dfs的返回值不是以当前节点为起点的最大路径和而是当前节点能向父节点贡献的最大增益。这个增益只能走一条边否则路径会分叉到父节点那里就拼不成一条直线了。这个区分如果不点破很多人会写成同时把左右两侧都返回给上层导致路径形状错误。4.3 序列化与反序列化唯一性重建的容错技巧序列化在实际工程里非常常见比如把一棵决策树存到数据库或者把菜单树结构传到前端。二叉树序列化最简单的做法是前序 空节点标记。我用X代表空节点用逗号做分隔符。反序列化的核心思路是使用一个全局索引按前序顺序逐步重建。每遇到一个X就返回None否则创建节点并递归构建左子树、右子树def deserialize(data): values data.split(,) index 0 def build(): nonlocal index if values[index] X: index 1 return None node TreeNode(int(values[index])) index 1 node.left build() node.right build() return node return build()这里一个非常容易踩的坑是全局索引的移动时机无论是空节点还是真实节点消费完当前值后都必须递增索引。很多人在空节点分支忘记递增导致同一个X被反复读取结构直接错乱。另外分隔符的选择也很讲究节点值如果可能包含逗号或换行就必须做转义或用JSON等结构化格式工程上这个细节能写出一篇单独的踩坑笔记。4.4 二叉搜索树的灵活性插入、删除与第K小BST题目最大的特点是可以利用有序性来剪枝和定位。插入操作很简单递归到空位时创建新节点但删除操作里有个经典的三情况分类被删节点是叶子、只有一个孩子、有两个孩子。前两种情况处理方式很直接第三种需要用右子树的最小节点或左子树的最大节点替换被删节点然后递归删除那个用于替换的节点def delete_node(root, key): if root is None: return None if key root.val: root.left delete_node(root.left, key) elif key root.val: root.right delete_node(root.right, key) else: if root.left is None: return root.right if root.right is None: return root.left min_node find_min(root.right) root.val min_node.val root.right delete_node(root.right, min_node.val) return root这个写法利用了BST的定义约束左子树所有节点都小于根右子树所有节点都大于根。所以找右子树最小节点时只要沿着左链一路走到底即可。删除时把min_node的值赋给当前节点再删掉右子树里那个最小节点这样既保持了BST的有序性又不用真的做复杂的指针拼接。工程里实现红黑树的删除会复杂得多但二叉搜索树版本的删除逻辑就是这一套。第K小元素可以用中序遍历也可以用带计数的递归。前者更通用因为代码直观不需要给节点增删字段def kth_smallest(root, k): stack, cur [], root while cur or stack: while cur: stack.append(cur) cur cur.left cur stack.pop() k - 1 if k 0: return cur.val cur cur.right这个迭代中序的套路在前面中序迭代部分已经搭好了这里直接把k作为计数器使用。注意k的减量时机是在弹出节点之后不要在压栈时就减。5. 我实际刷题中的避坑清单与题眼识别方法5.1 常见的六个隐蔽错误第一递归出口放错位置。很多人在进入函数第一步就写if root is None: return但有些题目的递归出口需要先判断当前节点是不是叶子再处理空节点。比如判断路径总和时如果你在空节点处返回False叶子节点永远不会被判断为路径结束结果有一个正确路径也会被漏掉。正确顺序是先判断空再判断叶子这两个出口不能合并。第二返回值类型不一致。有的分支返回节点有的分支返回布尔值。这种错误在编译器里能帮你查出来但在Python这种动态语言里只有运行时才会暴露而且往往在比较深层的递归里才报错。我建议在写递归函数的注释里明确写明这个函数的返回类型和语义格式不限自己看得懂就行。第三全局变量的引用问题。如果要在递归中修改一个list或dict直接用可变对象没问题但如果用的是int或str这类不可变对象修改操作实际创建了新对象不会影响外层作用域。解决方案是要么用可变容器包一层要么用嵌套函数加nonlocal关键字。这个坑我见过很多次尤其在统计路径总数、计算最大增益这类题目里。第四没有检查空树边界。任何二叉树题空树都必须作为独立用例考虑。递归函数里空节点通常能自然返回但层序遍历、序列化这些需要显式初始化的场景空树会直接返回空数组或空字符串不能报错。刷题前先问自己一句这题输入是None时应该输出什么第五左右子树的方向搞反。这个错误通常在题做多了、代码写快的时候出现。压栈顺序、递归参数传递、交换左右子树的题都要停下来画个简单例子验证一遍。画图真的比硬脑补可靠太多。第六过度使用全局变量导致多次调用状态污染。如果题目有多个测试用例而你的解法把上次运行的状态留在了全局变量里结果一定是错的。解决方法是把状态收集变量写进递归函数内部或者每次调用前显式重置。5.2 从题目关键词反推考点我刷了几百道二叉树题以后发现题目描述里的关键词基本能直接锁定解法方向。这里整理一张表方便你平时做题时对照题目常见表述核心考点推荐思路从根到叶子、路径之和DFS回溯或递归减法前序递归注意叶子出口最近公共祖先、任一子树中寻找自底向上聚合信息后序递归设计返回值语义逐层、每层、右侧视图BFS按层处理队列 每层固定长度最大深度、最小深度、高度树的深度定义与递归后序返回子树高度判断是否对称、翻转左右子树对称比较同时递归左左和右右第K小/大BST的中序有序性中序遍历或栈迭代序列化、重建、还原顺序编码与解码前序 空标记或层序二叉搜索树合法全局范围约束区间递归或中序检查路径和为target前缀和思想与回溯HashMap 前序展开为链表原地修改指针前序遍历记录节点表里最后一行前缀和思想值得多说一嘴。二叉树中的路径和如果允许任意起点到任意终点但不是类似最大路径和的任意形状而是垂直往下的路径用前缀和配合HashMap是标准解法这实际上是数组前缀和技巧在树结构上的迁移。你可以在遍历过程中维护从根到当前节点的累计值然后用当前累计值减去目标值看这个差值在不在HashMap里存在就说明此前某个祖先到当前节点之间的路径和正好等于目标值。理解了这一层你再看很多所谓的难题其实都是在已有算法模板上套了一个树的壳。5.3 关于递归转迭代的实战判断我见过很多人面试时陷入一个误区不管什么题上来就写递归结果被追问如果数据规模很大怎么办时一时语塞。我的建议是优先用递归写出清晰可验证的版本再在时间允许的情况下补一个迭代版本。原因很简单面试首先考察的是思路正确性递归版本最直观面试官也最好理解。迭代版本是加分项证明你清楚递归的代价和栈模拟的方法。但有几类题天生更适合迭代比如层序遍历必须用队列因为递归模拟层序反而要额外带level参数并且按层拼接结果代码更绕。再比如二叉树的深度虽然递归四行就能写完但如果树的形态接近于链表而数据量又大迭代版本更稳妥。事前判断这两条规律能省下很多现场纠结的时间。6. 按优先级排序的练习组合与复盘建议6.1 我建议的刷题顺序按依赖关系第一梯队是遍历四件套前序、中序、后序、层序。不要求背代码要求的是能随口说出递归和迭代两种写法的执行顺序并且能在三分钟内写出任意一种。这一层的标准不是做过而是闭眼能写。第二梯队是结构类操作翻转二叉树、对称判断、最大深度、最小深度、路径总和。这些题开始引入返回值语义和递归出口设计的概念是第一梯队的应用。做完这一层你对递归的理解会有一个质的提升。第三梯队是信息聚合类最近公共祖先、最大路径和、统计路径总数。这些题需要你理解子树的返回信息如何被父节点使用是二叉树算法里最难啃但最有价值的部分。第四梯队是序列化与重建前序序列化与反序列化、中序前序重建二叉树、中序后序重建二叉树、展开为链表。这些题考察的是结构唯一性和索引定位工程上用得也多。第五梯队是BST专项验证BST、第K小、插入删除、BST转累加树。这些题统一考察中序有序性和范围传递难度不算最高但细节多非常适合作为上机前的最终检查。6.2 复盘时问自己的三个问题每次刷完一道题我会强迫自己在题解旁边回答三个问题第一个问题这道题如果用递归它的当前节点职责是什么把这句话写在代码注释里。比如当前节点需要计算左右子树的最大增益并返回较大的那个。写不出这句话说明你对这题的理解还是模糊的。第二个问题如果去掉递归用栈或队列模拟代码结构会变成什么样不需要真的写出来但要在脑子里过一遍主要的指针操作。想不出来的题翻一翻前面的迭代模板十有八九是套得上的。第三个问题这道题的变式有哪些比如路径总和I根到叶子变到路径总和II要求输出所有路径再变到路径总和III任意起点每变一次递归函数参数或者返回值语义就要调整一次。能自己推导出这些变式的区别说明你真的理解了题目背后的模式。6.3 一个小技巧用极简输入验证代码正确性写完一道二叉树题别急着提交。先构造一个只有三个节点的最小树手动推演一遍。比如root是1左孩子2右孩子3。这样能快速验证前中后序的输出顺序是否正确、层序是否按层分组、递归出口有没有提前返回。再构造一个退化链1-2-3-4-5只有右孩子测试递归深度大时代码会不会崩、迭代版本是否能正常走完。这两类小用例基本能覆盖90%的边界问题。我自己的习惯是把这两个极简用例的预期结果直接写在题解的旁边哪怕过了测试也要再对一遍。因为Online Judge的测试用例通常覆盖全面但一旦报错你能拿到的报错信息往往不够直观手动推演反而能更快定位问题。这个习惯陪我走过了几十场在线笔试帮我节省了大量调试时间。7. 最后说点实际的二叉树算法的工程联想很多人在校招结束后就再也不碰二叉树题觉得这只是面试敲门砖。但我在实际工作中发现树的思维渗透在非常多系统设计里。举例来说一个复杂的业务规则引擎表达式本身就是抽象语法树一个菜单权限系统往往会用到树的层序和深度优先两种遍历做数据裁剪一个分布式缓存集群的哈希环本质上也是在树状结构上做路由。包括前端组件树、文件目录树、注释语法解析底层全是树的操作。所以我建议你把二叉树的学习定位成建立数据结构思维的核心一环而不只是应试工具。你真正要掌握的不是背诵某道题的答案而是如何把非线性结构的问题变成线性遍历中处理时机的选择问题。这个能力一旦建立它迁移到图、堆、Trie树、并查集上都是顺理成章的。根据我的个人经验二叉树题目的学习曲线是陡峭但短暂的前二十题会觉得吃力二十到五十题开始找到共性五十题之后大部分题你都能在五分钟内确定思路。关键点就是持续用返回值语义和处理时机这两个维度去拆解新题而不是为了数量刷题。你把这个习惯保持住哪怕隔了半年再看到二叉树相关算法也不会生疏到需要从头再来。
阅读完成 · 觉得有帮助？
