★ FEATURED ARTICLE 前几篇我们啃完了数组、链表、栈和队列进入树这个结构之后很多人会觉得“不就是长得像棵树嘛画出来就懂了”。可真到写代码、处理递归函数、调通遍历逻辑的时候画图和动手完全不是一回事。这一篇标题叫“12二叉树2”熟悉这个系列的朋友应该能猜出来这不是把二叉树从零再讲一遍而是讲我们在上一次基础之上怎么把二叉树真正变成可用的代码、可解的题目以及哪些坑是只靠看理论根本发现不了的。这篇文章适合两类人一类是刚学完二叉树定义但还没写过几段树相关代码的同学另一类是能看懂递归、但碰到“返回值应该设计成什么样”“什么时候用迭代什么时候用递归”就卡壳的人。我会尽量把每次实际写代码时的判断依据和踩坑过程写出来不是只扔一套模板而是让你有自己的思路。1. 为什么二叉树值得被单独拿出来“再讲一次”很多人在学数据结构的时候会觉得二叉树很尴尬数组、链表都直接对应着真实世界里的编号和排队树好像更抽象。但实际上二叉树是理解绝大多数递归算法的敲门砖。数组和链表的遍历看起来也是循环里走一遍但树的每个节点都藏着两个去向这意味着我们不能再靠“顺序”直觉而要开始习惯“分支”和“归并”。1.1 从一次模拟项目X的卡壳说起之前我在给一个内部组件做并发任务分层调度的时候任务之间不是线性的上下游关系而是一个不断分叉的结构。最开始的实现是用多层循环嵌套去匹配父子任务代码写得很长逻辑也很绕。后来换成了二叉树的思想把每个任务看作一个节点左右分支代表依赖的两个子时间片整个调度就变成一个先序遍历加状态合并的过程。当时我最大的感受是二叉树不是让你去背“怎么建一棵树”而是逼你用递归的思维方式重新看待“分叉”。很多人在这一步容易走偏以为二叉树就是要画出一个很复杂的树形图然后把每个节点都存在变量里。真正做项目的时候我们反复用的往往是树的抽象能力一个节点能拆成两个子问题子问题再继续拆。和递归的对应关系极强这是数组、链表给不了的训练。1.2 两种理解二叉树的视角物理形态和递归定义初学的时候我们会把二叉树想成“每个节点最多有两个孩子”的结构这是从布局角度理解。但写代码的时候我会建议你切换到递归定义二叉树要么是一个空节点要么是一个根节点加上左右两棵子树。这看起来像废话但它决定了你所有递归函数的基本骨架。因为一旦你接受了递归定义写任何树相关的函数都只需要考虑三件事当前节点空怎么办、当前节点做什么、左右子树返回什么结果给当前节点合并。我在带新人的时候会说别一上来去想整棵树是怎么处理的先想一个最小节点要做什么。可以说二叉树问题的本质不是树本身而是递归函数的设计。2. 动写代码前先把这些树的基本概念钉死标题里有个“2”说明我们默认你已经知道节点、根节点、叶子节点这些词。但在真写程序之前还有几个概念经常会让代码方向跑偏深度、高度、层数以及“完全二叉树”“满二叉树”“平衡二叉树”“退化二叉树”这些变体之间的区别。很多人觉得这些只是概念题但实际上它们直接影响到你用什么结构来存储、该不该用递归、以及遍历顺序要不要特殊处理。2.1 深度和高度的方向最容易搞反我见过太多人在计算树的深度和高度时把方向搞反包括我自己刚学的时候也栽过几次。节点的深度是从根节点到该节点经过的边数根节点深度是 0节点的高度是从该节点到叶子节点经过的最长路径边数叶子节点高度是 0。而整个树的高度就等于根节点的高度。为什么这个容易写错因为深度和高度在代码里常常都会变成“从递归返回结果里加一”。计算深度是自顶向下每往下传一层参数加一计算高度是自底向上左右子树返回较深的那一侧再加一。概念不钉死代码里就很容易把参数和返回值搞混。我的经验是出现一个树的递归函数先问自己“我是从上往下带参数还是从下往上返回状态”这一个问题能帮自己理清大半思路。2.2 几种特殊形态判断标准不要靠背这里列一个表是我在实际写树结构时常用来对照的形态判断标准工程实际用途满二叉树除了叶子节点每个节点都有左右孩子适合做哈夫曼树的讨论完全二叉树最后一层节点从左到右连续排列适合用数组存储比如堆平衡二叉树任意节点左右子树高度差不超过 1保证查找效率稳定退化二叉树每个节点只有一个孩子退化成链表递归时容易爆栈的典型很多算法题会嵌套这些概念比如求某棵树是不是完全二叉树或者判断是否平衡。遇到这类题不要死记结论而是回到定义去推导。你只要掌握“完全二叉树”和数组下标的对应关系后面学堆排序或者优先队列会轻松很多。3. 从零手写一棵二叉树节点的骨架和构建方式有了概念做底子我们该碰代码了。很多人习惯用别人封装好的树结构类但实际上自己手写一个最小的二叉树模型对理解遍历和递归特别有帮助。不需要多复杂的实现只要一个节点类和一个构建方式就够。3.1 一个最小可用的二叉树节点我用 Python 演示因为它在表达递归结构时最直白class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right这是我写算法题时最常用的一版就三个字段值、左孩子、右孩子。孩子默认为空是因为在 Python 里空节点用None表示最方便也能天然对应递归定义里的“空节点”终止条件。有人会问要不要保存父节点指针我的建议是做最简单的二叉树练习时不要加。加了父节点会让遍历写法变复杂而且很容易掩盖递归传参的问题。等后面做红黑树、AVL 这类需要向上回溯旋转的平衡树时再考虑加parent字段。3.2 手把手把一棵示例树搭出来我们用一个非常经典的树来做例子1 / \ 2 3 / \ \ 4 5 6写成代码最笨也最清晰的方式是手动创建每个节点node4 TreeNode(4) node5 TreeNode(5) node6 TreeNode(6) node2 TreeNode(2, node4, node5) node3 TreeNode(3, None, node6) root TreeNode(1, node2, node3)这段代码看起来像是在拼积木但它把“孩子也是节点”这件事表现得非常清楚。等你的代码量上来之后会慢慢习惯更简洁的写法比如从列表递归批量建树但初期动手把节点一个个 new 出来比直接调高级函数更有利于建立模型。3.3 二叉树的数组表示和序列化实际工程里二叉树不会总从节点对象开始很多时候是序列化字符串或数组。比如 LeetCode 风格的[1, 2, 3, null, null, 4, 5]它其实对应的是完全二叉树下标法某个节点在数组下标为i左孩子下标是2*i1右孩子下标是2*i2。但从这个列表恢复成树需要处理null的位置。我当时在写模拟项目X的数据解析模块时也碰到过这个问题起初用递归恢复树后来发现更稳妥的是用队列做 BFS 式建树。大致思路是先拿第一个元素做根然后逐层铺开遇到null就跳过但队列仍然记着当前待连接的节点位置。这个思路和层序遍历的代码是对称的学会它之后再反过来看层序遍历会特别顺。4. 遍历二叉树的需求和写法为什么顺序不能乱来遍历是二叉树最核心的操作后面前序、中序、后序在不同场景下的作用完全不同。前期很多人只是背一句“左根右”可真正动手写递归的时候却不知道根节点的打印在哪个位置。这一节我直接把递归和迭代两种写法都拆开并且重点说说哪些地方容易出问题。4.1 递归版三种深度优先遍历先看一组最小模板。假设我们要打印出每个节点的值def preorder(root): if root is None: return print(root.val, end ) preorder(root.left) preorder(root.right) def inorder(root): if root is None: return inorder(root.left) print(root.val, end ) inorder(root.right) def postorder(root): if root is None: return postorder(root.left) postorder(root.right) print(root.val, end )差别只有一个把打印语句放在递归前、两次递归中间还是放在递归之后。这就是根节点的处理时机。前序适合用来复制整棵树的结构因为你先处理根节点再去复制孩子中序在二叉搜索树里能输出递增序列因此经常出现在“判断是不是 BST”或“求第 K 小元素”的场景后序则特别适合释放树节点这种必须先处理完子树的场景也在很多计算树高度的题里用到。我强烈建议你把这三种遍历结果手动画一遍。对上面那棵示例树前序是1 2 4 5 3 6中序是4 2 5 1 3 6后序是4 5 2 6 3 1。不要硬背一旦你想清楚“根在什么时候打印”顺序自然就出来了。4.2 迭代版深度优先遍历显式栈的写法和坑面试和实际工程里递归并不是银弹。树退化成链表时递归可能会把调用栈打满而且有些语言想把遍历改成生成器用递归也不好处理。所以迭代遍历是绕不过去的。用显式栈模拟前序遍历最容易思路是每弹出一个节点先把右孩子压栈再压左孩子这样左孩子会先被取出来def preorder_iter(root): if root is None: return [] result [] stack [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很多人在迭代前序时以为处理顺序是“根左右”所以应该先压左孩子再压右孩子这就反了。栈是后进先出你想要左孩子先出来处理就必须最后压它。这个压栈顺序是迭代遍历里最经典的坑。中序迭代就更需要理解“去往最左边到底意味着什么”。它的标准套路是一路把左子树压栈直到遇到空节点然后弹出节点访问再把指针移到右子树继续。这个过程中栈里保存的其实是“待访问的根节点”而指针负责继续往左钻。4.3 层序遍历队列的一体两面层序遍历对应的数据结构是队列每一轮处理当前队列全部节点就能按层输出def level_order(root): if root is None: return [] result [] queue [root] while queue: level_size len(queue) current_level [] for _ in range(level_size): node queue.pop(0) current_level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) return result用pop(0)在 Python 列表里有点慢真实性能场景更常见的是用双端队列collections.deque这里为了演示逻辑先保持最直观的写法。层序和“从数组恢复二叉树”其实是互逆的过程我在本节开头提到过这个关系。建议你把这两个代码放在一起看一个是队列出队时把子节点入队一个是队列出队时把子节点挂到当前节点上思路完全一致。5. 二叉树题目的核心能力设计好递归返回值遍历只是基本功真正让二叉树变得有挑战性的是各种递归求解。我发现很多同学卡住的原因不是不会写递归而是没想清楚递归函数的“返回值到底代表什么”。这一节我会挑三个典型例子说明返回值的不同设计方式。5.1 求二叉树的最大深度返回子问题的较优解这个题的朴素定义如果节点为空高度为 0否则高度等于左右子树高度的最大值加 1。代码非常短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这里的关键在于函数返回的是“以当前节点为根的子树的最大深度”。它不关心父节点怎么调用它只要保证每个节点都按这个口径返回最终结果自然是对的。我在写这段代码时经常提醒自己不要试图在一个递归函数里同时完成“遍历”和“统计”很多件事一个函数先只解决一个问题。5.2 判断平衡二叉树状态合并要突破“单值返回”如果只是返回高度函数设计很简单。但判断一棵树是不是平衡的不仅要知道左右子树高度差是否超过 1还需要知道每一棵子树自己是否平衡。这意味着我们不能只返回一个布尔值必须在递归过程中同时带出两个信息。常见做法是用一个特殊值表示“不平衡”比如-1任何节点只要发现左右子树其中一个是-1或者高度差大于 1就直接返回-1def is_balanced(root): def height(node): if node is None: return 0 left_h height(node.left) right_h height(node.right) if left_h -1 or right_h -1 or abs(left_h - right_h) 1: return -1 return max(left_h, right_h) 1 return height(root) ! -1这个递归返回的并非单纯的“高度”而是一个复合状态要么是正常高度要么是“不合法”的哨兵值。很多二叉树题目都是这个套路像求二叉树的直径时直径可能不出现在递归路径的每一层而是需要有一个额外的变量去记录“某个节点作为转折点时的最大左右高度和”这让我养成了一个习惯先想清楚递归需要返回什么再决定要不要另开一个外部变量或闭包去跟踪全局最优值。5.3 序列化与反序列化为什么常常用递归实现如果你做过树的序列化会发现它天然就是前序遍历加上空节点标记。在递归序列化时函数返回的是一个字符串在反序列化时函数接收一个队列每次弹出当前节点对应的值然后递归构建左右子树。这套设计的巧妙之处在于两个递归函数是一一对应的镜像序列化是“输出根、递归左、递归右”反序列化是“读根、递归左、递归右”。你要是把前序遍历写熟了这一块基本就是白送的分。5.4 递归返回的另一种常见设计自底向上与自顶向下除了返回值我们还要区分方向。有些二叉树问题适合自顶向下比如计算从根到某个节点的路径和可以带着“已有的路径和”往下传参数。有些问题适合自底向上比如最大深度、直径、是否平衡这些都必须等左右子树算完才能决定当前节点。我在实际看别人代码时发现一个很典型的错误该用参数传递状态的时候却试图把中间结果存在返回值里该用返回值合并子树信息的时候却又在外部定义变量到处改。想要少踩这些坑我的经验是凡是要依赖子树结果才能得到当前答案的一律考虑用返回值凡是要根据父路径信息去限制当前节点搜索范围的比如 BST 的范围校验优先考虑往下传参数。6. 二叉树的那些“变异亲戚”从专属结构到普适问题聊完手写代码的细节我们把视角放宽一点。二叉树的变体实在是太多了二叉搜索树、堆、AVL 树、红黑树、线段树、Trie很多看着很高级的数据结构底层都是二叉树的思维变种。这一章不是说要把它们全部实现一遍而是帮你建立选择意识什么场景用哪种树以及为什么工程上看到的树和算法题里的“裸二叉树”不完全一样。6.1 二叉搜索树为什么能加速查找二叉搜索树要求左子树所有值小于根右子树所有值大于根。这个约束让每一层查找都能丢掉一半的搜索区间和二分查找有点像。但要注意这只是理想情况如果插入顺序刚好是递增的树会退化成链表查找效率变成线性的。这就是为什么工程上很少用裸 BST而是用 AVL 树、红黑树这些带平衡约束的变种。我在学习的时候总觉得红黑树很复杂后来再想它的本质其实是“用一套严格得不近人情的规则尽量让树保持矮胖避免各种插入删除操作导致退化”。理解了这一点各种旋转操作就不那么玄乎了。6.2 完全二叉树和堆的关系堆是一种完全二叉树而且分为大顶堆和小顶堆。因为完全二叉树可以通过数组按层存储所以堆可以不用真正的“节点对象”直接用下标访问父子。这个特性让堆在实现优先队列时非常节约内存也更快。很多堆排序的代码从形态上看根本没有TreeNode只有数组和下标初学者容易把堆和二叉树隔绝起来。其实堆就是躲在数组里的完全二叉树。我曾经写过一个优先队列调度模块最开始用的普通链表后来改成用数组实现堆队列长度几万的时候性能差距非常明显。这就是为什么我建议你在学堆之前先好好理解完全二叉树的层序编号规则。6.3 多叉树、森林和二叉树的转换项目里真正见到的树常常不是二叉的比如某个跨平台系统里的菜单权限树一个父节点底下可能有五六个子节点。处理这种多叉树一种思路是转成二叉树第一个孩子作为左孩子下一个兄弟作为右孩子也就是“左孩子右兄弟”表示法。这套表示法在文件系统、编译器语法树上都很常见。它能让节点的“最多两个孩子”这个限制化解掉绝大部分多叉问题。我和同事看旧代码时遇到过一棵几十层的菜单树最后就是用这个思路把递归遍历统一成了二叉树遍历逻辑代码量立刻缩了一大截。7. 真调二叉树代码时最常见的几个隐蔽错误理论讲得再多没有实际跑过代码还是会踩坑。这里说几个我真实遇到过的错误有些看起来特别低级甚至会被 IDE 警告但它们非常容易在加班到深夜的时候冒出来。7.1 递归没有处理空节点或者处理得太晚最基础的错误就是进入递归函数不先判断节点是不是None直到访问node.left才报空指针异常。正确的习惯是函数最前面就处理空节点把“空节点是最小子问题”放在心里。如果是递归中要判断节点值是否等于某个目标值也要想清楚当root.val为 null 时的短路顺序。还有一个容易被忽视的场景递归函数里一个分支已经发现空节点了但错误地继续尝试返回一个有效值。比如求最小深度时如果左子树为空而右子树不为空最小深度并不是min(0, right_depth) 1而应该是right_depth 1。我在初学时在这里错了好几次因为只看“取最小值”这个泛化逻辑没考虑实际树形结构。7.2 用递归处理退化树导致爆栈当一棵二叉树退化成链表比如每个节点都只有右孩子递归深度会直接达到节点个数。数据量稍微大一点调用栈就会撑不住。我遇到过线上一个告警统计任务树结构因为某次配置错误变成了深度十几万的链递归一调用直接栈溢出服务挂掉好一阵。现在的解决思路一般有两类一是把递归改成显式栈或队列的迭代版本二是在构建时限制树的平衡。对于大多数算法练习显式栈更通用尤其是前序、中序的迭代栈写起来并不难。我个人的习惯是预估深度可能超过一万的树默认先写迭代只有明确知道是一棵矮树才敢于用递归偷懒。7.3 把 Python 列表当作队列用为了演示方便很多教程会用list.pop(0)来模拟队列但如果数据量大它的复杂度是 O(n)因为每次弹出都会移动后面所有元素。生产环境我一般直接用collections.deque。这个点经常被不够严谨的博客带偏但做层序遍历时一旦数据量上来差距会立刻体现。还有一个容易被忽略的点如果你在迭代遍历时不断往列表里 append 节点然后又要按索引访问必须考虑节点数量和内存占用。树的节点多到一定程度对象引用本身也是一笔内存开销建议在写代码前想清楚是“数组下标模拟树”还是“对象节点树”更适合当前场景。7.4 递归里误改全局变量在二叉树问题里有时候我们会用全局变量去记录最大值或者累积值比如求路径总和。如果递归不小心把全局变量重置或者在不同分支之间没有按预期恢复结果就会变得非常随机。我的建议是先尽量用返回值传递状态实在需要外部变量时用闭包或实例属性都比全局裸变量更可控。8. 我写二叉树代码时养成的小习惯乱七八糟的坑讲完最后分享几个我自己长期用下来的小习惯。这些习惯不一定适合所有人但确实帮我减少了很多低级错误。第一个习惯是每写一个树相关的递归函数我都会先写空节点判断再写当前节点要做的事最后才去想怎么调用左右子树。这个顺序看起来简单却能让函数骨架非常稳定。第二个习惯是在纸上先画一棵只有三五个节点的树然后手动走一遍递归过程把每个节点的深度或返回值标上去。很多看起来特别绕的题目走一遍小例子之后就没什么神秘感了。第三个习惯是用“返回值设计”作为切入点而不是“遍历顺序”。很多新手看到递归题就问“这是前序还是中序”我建议先问“这个函数要向上返回什么东西”。拿求最大直径来说如果只想“要遍历所有节点”方向就很模糊但如果明确“向下递归返回单侧最大长度向上还要用一个外部变量记录左右相加的最大值”代码立刻就清晰了。二叉树这块内容确实容易让人产生“会了”的错觉画图的时候一切了然于心一写代码就原形毕露。我的体会是树的问题就是递归的问题而递归的问题就是函数设计和状态传递的问题。你不需要一次背下几百道树题能把一个节点的子问题想透彻再复杂的树也不过是这个模式反复堆叠。后面如果想进阶可以自己动手写一棵带平衡操作的二叉搜索树或者用数组实现一个堆这些都是在“12二叉树2”之后非常好的下一步练手。
阅读完成 · 觉得有帮助？
