最近在帮团队做代码评审的时候发现一个很有意思的现象很多写了好几年业务的同学一碰到二叉树相关的需求就有点发怵。其实也不怪他们日常开发里链表都未必天天写更别说二叉树了。但无论是面试也好还是真的遇到一些需要组织层级数据、做表达式解析、搞搜索树优化的场景二叉树永远绕不开两个核心操作——遍历和旋转。这篇就当是一份实操笔记来写。我不会给你堆一堆学院派的理论而是把我自己从手写遍历到实现 AVL 树这整个过程中真正踩过的坑、验证过的方法、觉得好用的套路全部摊开来说。内容分为几大块先聊聊为什么遍历和旋转是二叉树的命门然后把四种遍历方式从递归到迭代逐个拆解接着进入重头戏——旋转操作从单旋到双旋每一种我都会配图配合代码讲清楚最后再分享一些你在教科书上看不到的问题排查技巧。1. 整体设计与思路拆解1.1 为什么遍历和旋转是二叉树的“命门”二叉树这个结构本身其实不复杂。就是一个节点最多两个分支左孩子右孩子仅此而已。但你真把它用起来就会发现几乎所有关键操作都落在两件事上一是怎么把树里的节点按某种顺序摸一遍这就是遍历二是怎么在插入、删除之后把树重新弄平衡别让它退化成一条链表这就是旋转。先说遍历这件事。很多初学者会觉得遍历不就是递归三板斧嘛先序中序后序背下来就行。但实际场景里遍历承载的语义远不止“把数据打出来”。比如你要用二叉树做表达式求值中序遍历拿到的是中缀表达式后序遍历拿到的是后缀表达式选错遍历方式整个算法的正确性就没了。再比如你要把一棵二叉树序列化存储到数据库或者通过接口传输给前端前序遍历往往是最方便的。还有层序遍历它天然适配按层展示、广度优先搜索、求树的宽度这类需求。可以说遍历不仅是理解二叉树结构的入口更是很多高级算法的基础设施。再说旋转。二叉搜索树在理想情况下查找时间复杂度是 O(log n)但这是建立在一棵“平衡”的树之上的。如果你按照已排序的顺序往树里插入数据树会直接退化成链表查找变成 O(n)性能直接崩掉。旋转就是用来拯救这件事的。通过左旋、右旋以及它们的组合我们可以在保持二叉搜索树“左小右大”性质不变的前提下把树的高度压下来让它重新变得平衡。AVL 树、红黑树这两个工业级常用的平衡树结构底层核心操作就是旋转。所以你看遍历解决的是“怎么读”的问题旋转解决的是“怎么保持健康”的问题。一个管信息提取一个管结构稳定两个加起来才构成一棵二叉树从创建到使用到维护的完整闭环。这篇笔记的思路就是先打通遍历再攻克旋转最后一并解决两者配合时会遇到的坑。1.2 先建立直觉遍历顺序的三种“视角”与旋转的“轴心思维”在动手写代码之前我更建议你先在脑子里建立一个直觉模型。对于遍历你只需要记住一句话先序、中序、后序这三个名字说的是根节点被访问的时机。先序就是先访问根再管左子树和右子树中序就是先管左子树再访问根最后管右子树后序则是先管完左右子树最后才轮到根。你不需要死记“前序是根左右”这种口诀你只需要理解“根的位置”。而且有一个非常重要的直觉中序遍历一棵二叉搜索树得到的结果一定是有序的。这是后面很多验证手段的理论基础。对于旋转你需要建立的是“轴心思维”。所谓左旋想象你用手拎起某个节点作为新的根然后把它原来的父节点“沉”到它的左侧。反过来右旋就是拎起另一个节点作为新根把原来的父节点“沉”到右侧。旋转本身不改变节点之间的中序顺序它改变的只是树的形状和高度。一旦你建立了这个轴心的画面感LL、RR、LR、RL 四种失衡场景就很好理解了LL 就是左边太重需要向右旋RR 就是右边太重需要向左旋LR 和 RL 这种拐弯的形态则必须先旋一次把它掰直再朝反方向旋一次把它压平。有了这两个直觉后面的代码就不是背了而是顺着思路“长”出来的。2. 遍历实操四种方式从递归到迭代的完整落地2.1 递归实现五分钟写出三种经典遍历递归版本的遍历是理解二叉树最自然的方式。代码量极少核心逻辑就是函数自己调用自己。我直接给出一份可以直接跑起来的 Python 实现class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right # 前序遍历根 - 左 - 右 def preorder_recursive(root): if not root: return [] return [root.val] preorder_recursive(root.left) preorder_recursive(root.right) # 中序遍历左 - 根 - 右 def inorder_recursive(root): if not root: return [] return inorder_recursive(root.left) [root.val] inorder_recursive(root.right) # 后序遍历左 - 右 - 根 def postorder_recursive(root): if not root: return [] return postorder_recursive(root.left) postorder_recursive(root.right) [root.val]这里我想多说一句很多教材喜欢用“访问根节点”这个说法初学者容易被“访问”两个字搞晕其实这里就是“把当前节点的值收集起来塞进结果列表”。递归版本虽然简单但它有一个隐患就是当树的深度比较大比如几十万层退化成链表时递归调用栈会溢出。所以下面迭代版本必须掌握。2.2 迭代实现显式栈模拟彻底摆脱递归深度限制迭代版本的核心思想就是用自己管理的栈来模拟系统递归调用栈。前序遍历和中序遍历非常像差别只在访问节点的时机。我先给出前序和中序的迭代写法# 前序遍历迭代版 def preorder_iterative(root): if not root: return [] stack [root] result [] while stack: node stack.pop() if node: result.append(node.val) # 先压右子树再压左子树 # 因为栈是后进先出左子树后压下次循环先弹出 stack.append(node.right) stack.append(node.left) return result # 中序遍历迭代版 def inorder_iterative(root): result [] stack [] current root while stack or current: while current: # 一路向左把所有左孩子压栈 stack.append(current) current current.left # 当前节点没有左孩子了弹出并访问 current stack.pop() result.append(current.val) # 转向右子树 current current.right return result这里必须提醒一个关键点前序遍历迭代版本中压栈顺序是“先右后左”。很多初学者容易搞反写成先左后右结果就是访问顺序变成“根右左”完全错误。你可以这么理解栈是后进先出的我们希望左子树先被访问到那它就应该是后压栈的那个这样才能在下一次 pop 时先出来。再看后序遍历的迭代版本。这个稍微绕一点因为后序的顺序是“左右根”根是最后访问的。一个讨巧但非常实用的技巧是先做一次“根右左”的遍历相当于前序遍历时先把左孩子压栈然后把结果反转就得到了“左右根”。# 后序遍历迭代版借助前序遍历的变形 反转 def postorder_iterative(root): if not root: return [] stack [root] result [] while stack: node stack.pop() if node: result.append(node.val) # 这里先压左子树再压右子树 stack.append(node.left) stack.append(node.right) # 此时 result 是 根-右-左反转得到 左-右-根 return result[::-1]这个方法我强烈推荐它几乎不增加任何记忆成本只需要在写前序迭代时把左右压栈顺序对调最后加一行反转就搞定了后序。而且性能上没有任何额外损耗比那种用额外栈记录访问状态的繁琐写法清爽太多了。2.3 层序遍历队列实现一个 while 循环搞定一层层序遍历和前三种不太一样它是一层一层水平扫描的天然适合用队列来做。为什么用队列因为我们需要“先进先出”的顺序先把根放进去然后弹出根、把它的左右孩子依次放进队尾再从头弹出下一个节点这样就能保证每一层都是从左到右的。from collections import deque def level_order(root): if not root: return [] queue deque([root]) result [] while queue: level_size len(queue) current_level [] for _ in range(level_size): node queue.popleft() 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注意这里我用了一个level_size len(queue)的技巧先把当前层的节点数存下来然后只处理这么多节点这样current_level收集到的就恰好是一整层的节点。很多同学遇到“按层输出”的需求就慌其实关键就是这一行。这个写法在处理二叉树深度、层宽度等问题时非常好用。2.4 由先序中序确定一棵树的完整推导过程前面聊的都是“给定树求遍历序列”。但实际面试里还有一个高频的反向操作已知先序和中序还原整棵树。这个需求在真实项目中也有价值比如你从前端拿到一个序列化的树形数据前序中序要在后端重建这棵树的时候就需要这个能力。核心原理其实就一条前序遍历的第一个元素一定是整棵树的根然后拿着这个根的值去中序序列里找位置根左边的全是左子树根右边的全是右子树。接着递归下去就恢复了整棵树。我用代码实现一下def build_tree_from_pre_in(preorder, inorder): if not preorder or not inorder: return None root_val preorder[0] root TreeNode(root_val) root_idx inorder.index(root_val) left_inorder inorder[:root_idx] right_inorder inorder[root_idx 1:] left_preorder preorder[1:1 len(left_inorder)] right_preorder preorder[1 len(left_inorder):] root.left build_tree_from_pre_in(left_preorder, left_inorder) root.right build_tree_from_pre_in(right_preorder, right_inorder) return root这里需要注意一个细节每次递归时左子树的前序序列长度必须和左子树的中序序列长度相等。所以要先通过中序算出左子树的长度再去前序里切出对应长度的部分。直接拿preorder[1:]当左子树的前序是很多初学者常犯的错误。同理已知后序中序也可以重建树思路一致只是根是后序序列的最后一个元素感兴趣的话可以自己推一遍。3. 旋转实操从 AVL 树到平衡维护的核心环节3.1 什么情况下需要旋转先读懂四种失衡场景旋转不是凭空来的它只在一个特定场景下触发树失衡了。什么叫失衡对二叉搜索树来说通常我们关注每个节点的左右子树高度差。在 AVL 树以发明者 Adelson-Velsky 和 Landis 命名的自平衡二叉搜索树里这个差值绝对值不能超过 1。一旦超过就失衡了需要旋转。失衡场景一共有四种我用最直白的语言描述LL 型某个节点的左子树的左子树太重了。通俗说就是“左左太重”。矫正方法是右旋。RR 型某个节点的右子树的右子树太重了。“右右太重”矫正方法是左旋。LR 型某个节点的左子树的右子树太重了。这是拐弯的形态需要先对左子树做左旋把它变成 LL 型再对根做右旋。RL 型某个节点的右子树的左子树太重了。先对右子树做右旋再对根做左旋。这里我建议你画一张图把四个场景的树形画出来。你会发现一个规律LL 和 RR 是一条直线下来的LR 和 RL 是先折一下的。直线型的只需要一次旋转折线型的需要两次。这比死记硬背强多了。3.2 左旋与右旋代码实现每一步都要画图对照先看右旋。右旋的核心操作是把当前节点的左孩子提上来当新根当前节点变成新根的右孩子新根原来的右孩子过继给当前节点当左孩子。写成代码def right_rotate(y): # 右旋y 是失衡的根节点 x y.left T2 x.right # 旋转 x.right y y.left T2 # 更新高度后面会讲 y.height 1 max(get_height(y.left), get_height(y.right)) x.height 1 max(get_height(x.left), get_height(x.right)) return x左旋就是完全镜像的操作把当前节点的右孩子提上来当新根当前节点变成新根的左孩子新根原来的左孩子过继给当前节点当右孩子def left_rotate(x): y x.right T2 y.left y.left x x.right T2 x.height 1 max(get_height(x.left), get_height(x.right)) y.height 1 max(get_height(y.left), get_height(y.right)) return y这两个函数是整个 AVL 树的发动机。你需要注意旋转完成后一定记得更新参与旋转节点的高度否则后续的平衡因子计算就是错的树的失衡判断也会跟着错。我最早实现 AVL 树时就是漏了高度更新结果插入十几个节点后树就莫名其妙不平衡了。3.3 双旋是怎么组合的LR 与 RL 的完整推导双旋其实不是新的操作就是两次单旋的组合。LR 型即左子树的右子树失衡我们分两步走先对失衡根节点的左孩子做一次左旋此时整棵树变成 LL 型再对失衡根节点做一次右旋。def insert_and_balance(root, key): # 标准 BST 插入 if not root: return TreeNode(key) if key root.val: root.left insert_and_balance(root.left, key) elif key root.val: root.right insert_and_balance(root.right, key) else: return root # 更新高度 root.height 1 max(get_height(root.left), get_height(root.right)) # 计算平衡因子 balance get_balance(root) # LL 型 if balance 1 and key root.left.val: return right_rotate(root) # RR 型 if balance -1 and key root.right.val: return left_rotate(root) # LR 型 if balance 1 and key root.left.val: root.left left_rotate(root.left) return right_rotate(root) # RL 型 if balance -1 and key root.right.val: root.right right_rotate(root.right) return left_rotate(root) return root这里平衡因子的计算方式是左子树高度减去右子树高度。大于 1 说明左边沉了小于 -1 说明右边沉了。为什么还要判断 key 和 root.left.val / root.right.val 的关系因为我们要确定新插入的节点到底是在左子树的左边还是右边以此区分是 LL 还是 LR。这是 AVL 树插入代码最核心的分支判断也是很多人容易写混的地方。3.4 一个模拟插入的完整过程感受平衡因子的变化理论说多了容易飘我直接带你在一个具体序列上走一遍 AVL 树的插入过程。假设依次插入30, 20, 10, 40, 50。插入 30根节点高度 1。插入 2020 小于 30成为左孩子30 的平衡因子变 1没失衡。插入 1010 小于 20成为 20 的左孩子。此时 30 的左子树高度 2右子树高度 0平衡因子 2失衡。判断10 小于 20属于 LL 型对 30 做右旋。旋转后 20 成为根30 成为 20 的右孩子10 保持为 20 的左孩子。插入 4040 大于 20 且大于 30成为 30 的右孩子。此时 20 的右子树高度 2左子树高度 1平衡因子 0没事。插入 5050 大于 30成为 40 的右孩子。此时 30 的平衡因子 -2右子树高度 2左子树高度 0失衡。判断50 大于 40属于 RR 型对 30 做左旋。旋转后 40 成为 20 的右孩子30 成为 40 的左孩子50 保持为 40 的右孩子。你可以在纸上把这棵树画出来感受一下旋转如何通过局部的结构调整让整体高度维持在 log n 的量级。整个过程中中序遍历序列始终是 [10, 20, 30, 40, 50]——旋转没有破坏搜索树的有序性质。这一点是验证旋转是否正确的黄金标准强烈建议你每次写完旋转操作后都用中序遍历检查一次结果。4. 常见问题与排查技巧实录4.1 遍历相关递归栈溢出与迭代死循环遍历最常见的问题有两个。第一个是递归深度过大导致栈溢出这个前面提过了解决办法就是把递归改成显式栈的迭代版本。实际工程里如果你的树是严重偏斜的深度可能达到几十万层递归必定爆栈迭代版本就不会。第二个是迭代中序遍历容易写出死循环。最常见的原因是 while 循环里忘记移动current。我再强调一遍在处理完左子树并弹出节点后一定要把current指向node.right哪怕它是空节点。这样下一轮循环要么从stack继续弹要么从current继续往下走两个条件缺一个都会导致循环无法终止。4.2 旋转相关高度更新遗漏与平衡因子计算混乱旋转出 bug 的高发区第一个就是忘记更新高度。很多初学者在完成节点指针的交换后觉得整个旋转就完事了结果调试时发现平衡因子始终不对。记住只要树的结构变了涉及节点的子树高度就可能变必须在旋转函数内部更新高度。第二个高发区是平衡因子的正负号约定不统一。有的资料用“左减右”有的用“右减左”导致 LL 和 RR 的判断逻辑完全是反的。我的建议是固定用“左子树高度 - 右子树高度”并且固定以大于 1 和小于 -1 作为判断阈值。写代码前先把这个约定写在注释里避免自己把自己绕晕。4.3 定位问题的通用思路用中序遍历做“体检”最后分享一个我这些年调试二叉树问题屡试不爽的万能排查思路。不管你的树看起来多乱只要做两件事第一跑一次中序遍历检查结果是否是有序的。如果无序说明 BST 性质被破坏了问题一定出在插入或旋转时的比较逻辑如果有序说明树结构本身没问题接下来再去查高度和平衡因子的计算。第二写一个递归函数动态计算每个节点的左右子树高度差。如果发现某个节点高度差绝对值大于 1就沿着这个节点的路径找到最低的失衡节点再判断它的孩子节点是哪边高、孙子节点是哪边高从而确定是 LL、RR、LR、RL 中的哪一种照对应的旋转方式修复。这个方法配合调试器使用基本能解决 90% 的二叉树疑难杂症。4.4 一组“深坑”速查表症状大概率原因排查方向中序遍历结果不是升序插入时比较符号写反 / 旋转时把左右子树接错打印插入路径检查每个节点与父节点的比较逻辑前序遍历迭代输出顺序错乱压栈顺序反了应先压右子树再压左子树检查压栈顺序后序遍历结果和递归版本不一致反转前的遍历顺序写得不对先手动模拟一棵三层小树对比节点顺序树的高度越插越大旋转后没有更新节点高度检查 rotate 函数内部是否有 height 更新语句插入后根节点一直不变旋转函数的返回值没有被赋值给插入函数上一层检查递归赋值是否是root.left insert_and_balance(root.left, key)层序遍历各层节点混杂没有在每轮循环开始时固定level_size用len(queue)缓存层大小最后说几句体己话这些东西看着多但真正动手写一遍之后你会发现二叉树没有那么玄。遍历也好旋转也好本质都是对节点指针的重新整理画图比背代码有用十倍。我个人每次写 AVL 树之前都会先在草稿纸上画一棵五节点的树手动模拟一轮插入和旋转再去写代码这个习惯帮我减少了很多不必要的 debug 时间。另外调试二叉树最有力的工具不是打印函数而是可视化树的结构——找一个支持树形输出的调试插件或者自己写一个简单的层序遍历打印比盯着数组结果猜问题快得多。希望这篇笔记能帮你少走一些我当年走过的弯路把遍历和旋转真正变成一个肌肉记忆级别的基本功。
二叉树遍历与旋转操作实战：从递归到AVL树的自平衡机制
最近在帮团队做代码评审的时候发现一个很有意思的现象很多写了好几年业务的同学一碰到二叉树相关的需求就有点发怵。其实也不怪他们日常开发里链表都未必天天写更别说二叉树了。但无论是面试也好还是真的遇到一些需要组织层级数据、做表达式解析、搞搜索树优化的场景二叉树永远绕不开两个核心操作——遍历和旋转。这篇就当是一份实操笔记来写。我不会给你堆一堆学院派的理论而是把我自己从手写遍历到实现 AVL 树这整个过程中真正踩过的坑、验证过的方法、觉得好用的套路全部摊开来说。内容分为几大块先聊聊为什么遍历和旋转是二叉树的命门然后把四种遍历方式从递归到迭代逐个拆解接着进入重头戏——旋转操作从单旋到双旋每一种我都会配图配合代码讲清楚最后再分享一些你在教科书上看不到的问题排查技巧。1. 整体设计与思路拆解1.1 为什么遍历和旋转是二叉树的“命门”二叉树这个结构本身其实不复杂。就是一个节点最多两个分支左孩子右孩子仅此而已。但你真把它用起来就会发现几乎所有关键操作都落在两件事上一是怎么把树里的节点按某种顺序摸一遍这就是遍历二是怎么在插入、删除之后把树重新弄平衡别让它退化成一条链表这就是旋转。先说遍历这件事。很多初学者会觉得遍历不就是递归三板斧嘛先序中序后序背下来就行。但实际场景里遍历承载的语义远不止“把数据打出来”。比如你要用二叉树做表达式求值中序遍历拿到的是中缀表达式后序遍历拿到的是后缀表达式选错遍历方式整个算法的正确性就没了。再比如你要把一棵二叉树序列化存储到数据库或者通过接口传输给前端前序遍历往往是最方便的。还有层序遍历它天然适配按层展示、广度优先搜索、求树的宽度这类需求。可以说遍历不仅是理解二叉树结构的入口更是很多高级算法的基础设施。再说旋转。二叉搜索树在理想情况下查找时间复杂度是 O(log n)但这是建立在一棵“平衡”的树之上的。如果你按照已排序的顺序往树里插入数据树会直接退化成链表查找变成 O(n)性能直接崩掉。旋转就是用来拯救这件事的。通过左旋、右旋以及它们的组合我们可以在保持二叉搜索树“左小右大”性质不变的前提下把树的高度压下来让它重新变得平衡。AVL 树、红黑树这两个工业级常用的平衡树结构底层核心操作就是旋转。所以你看遍历解决的是“怎么读”的问题旋转解决的是“怎么保持健康”的问题。一个管信息提取一个管结构稳定两个加起来才构成一棵二叉树从创建到使用到维护的完整闭环。这篇笔记的思路就是先打通遍历再攻克旋转最后一并解决两者配合时会遇到的坑。1.2 先建立直觉遍历顺序的三种“视角”与旋转的“轴心思维”在动手写代码之前我更建议你先在脑子里建立一个直觉模型。对于遍历你只需要记住一句话先序、中序、后序这三个名字说的是根节点被访问的时机。先序就是先访问根再管左子树和右子树中序就是先管左子树再访问根最后管右子树后序则是先管完左右子树最后才轮到根。你不需要死记“前序是根左右”这种口诀你只需要理解“根的位置”。而且有一个非常重要的直觉中序遍历一棵二叉搜索树得到的结果一定是有序的。这是后面很多验证手段的理论基础。对于旋转你需要建立的是“轴心思维”。所谓左旋想象你用手拎起某个节点作为新的根然后把它原来的父节点“沉”到它的左侧。反过来右旋就是拎起另一个节点作为新根把原来的父节点“沉”到右侧。旋转本身不改变节点之间的中序顺序它改变的只是树的形状和高度。一旦你建立了这个轴心的画面感LL、RR、LR、RL 四种失衡场景就很好理解了LL 就是左边太重需要向右旋RR 就是右边太重需要向左旋LR 和 RL 这种拐弯的形态则必须先旋一次把它掰直再朝反方向旋一次把它压平。有了这两个直觉后面的代码就不是背了而是顺着思路“长”出来的。2. 遍历实操四种方式从递归到迭代的完整落地2.1 递归实现五分钟写出三种经典遍历递归版本的遍历是理解二叉树最自然的方式。代码量极少核心逻辑就是函数自己调用自己。我直接给出一份可以直接跑起来的 Python 实现class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right # 前序遍历根 - 左 - 右 def preorder_recursive(root): if not root: return [] return [root.val] preorder_recursive(root.left) preorder_recursive(root.right) # 中序遍历左 - 根 - 右 def inorder_recursive(root): if not root: return [] return inorder_recursive(root.left) [root.val] inorder_recursive(root.right) # 后序遍历左 - 右 - 根 def postorder_recursive(root): if not root: return [] return postorder_recursive(root.left) postorder_recursive(root.right) [root.val]这里我想多说一句很多教材喜欢用“访问根节点”这个说法初学者容易被“访问”两个字搞晕其实这里就是“把当前节点的值收集起来塞进结果列表”。递归版本虽然简单但它有一个隐患就是当树的深度比较大比如几十万层退化成链表时递归调用栈会溢出。所以下面迭代版本必须掌握。2.2 迭代实现显式栈模拟彻底摆脱递归深度限制迭代版本的核心思想就是用自己管理的栈来模拟系统递归调用栈。前序遍历和中序遍历非常像差别只在访问节点的时机。我先给出前序和中序的迭代写法# 前序遍历迭代版 def preorder_iterative(root): if not root: return [] stack [root] result [] while stack: node stack.pop() if node: result.append(node.val) # 先压右子树再压左子树 # 因为栈是后进先出左子树后压下次循环先弹出 stack.append(node.right) stack.append(node.left) return result # 中序遍历迭代版 def inorder_iterative(root): result [] stack [] current root while stack or current: while current: # 一路向左把所有左孩子压栈 stack.append(current) current current.left # 当前节点没有左孩子了弹出并访问 current stack.pop() result.append(current.val) # 转向右子树 current current.right return result这里必须提醒一个关键点前序遍历迭代版本中压栈顺序是“先右后左”。很多初学者容易搞反写成先左后右结果就是访问顺序变成“根右左”完全错误。你可以这么理解栈是后进先出的我们希望左子树先被访问到那它就应该是后压栈的那个这样才能在下一次 pop 时先出来。再看后序遍历的迭代版本。这个稍微绕一点因为后序的顺序是“左右根”根是最后访问的。一个讨巧但非常实用的技巧是先做一次“根右左”的遍历相当于前序遍历时先把左孩子压栈然后把结果反转就得到了“左右根”。# 后序遍历迭代版借助前序遍历的变形 反转 def postorder_iterative(root): if not root: return [] stack [root] result [] while stack: node stack.pop() if node: result.append(node.val) # 这里先压左子树再压右子树 stack.append(node.left) stack.append(node.right) # 此时 result 是 根-右-左反转得到 左-右-根 return result[::-1]这个方法我强烈推荐它几乎不增加任何记忆成本只需要在写前序迭代时把左右压栈顺序对调最后加一行反转就搞定了后序。而且性能上没有任何额外损耗比那种用额外栈记录访问状态的繁琐写法清爽太多了。2.3 层序遍历队列实现一个 while 循环搞定一层层序遍历和前三种不太一样它是一层一层水平扫描的天然适合用队列来做。为什么用队列因为我们需要“先进先出”的顺序先把根放进去然后弹出根、把它的左右孩子依次放进队尾再从头弹出下一个节点这样就能保证每一层都是从左到右的。from collections import deque def level_order(root): if not root: return [] queue deque([root]) result [] while queue: level_size len(queue) current_level [] for _ in range(level_size): node queue.popleft() 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注意这里我用了一个level_size len(queue)的技巧先把当前层的节点数存下来然后只处理这么多节点这样current_level收集到的就恰好是一整层的节点。很多同学遇到“按层输出”的需求就慌其实关键就是这一行。这个写法在处理二叉树深度、层宽度等问题时非常好用。2.4 由先序中序确定一棵树的完整推导过程前面聊的都是“给定树求遍历序列”。但实际面试里还有一个高频的反向操作已知先序和中序还原整棵树。这个需求在真实项目中也有价值比如你从前端拿到一个序列化的树形数据前序中序要在后端重建这棵树的时候就需要这个能力。核心原理其实就一条前序遍历的第一个元素一定是整棵树的根然后拿着这个根的值去中序序列里找位置根左边的全是左子树根右边的全是右子树。接着递归下去就恢复了整棵树。我用代码实现一下def build_tree_from_pre_in(preorder, inorder): if not preorder or not inorder: return None root_val preorder[0] root TreeNode(root_val) root_idx inorder.index(root_val) left_inorder inorder[:root_idx] right_inorder inorder[root_idx 1:] left_preorder preorder[1:1 len(left_inorder)] right_preorder preorder[1 len(left_inorder):] root.left build_tree_from_pre_in(left_preorder, left_inorder) root.right build_tree_from_pre_in(right_preorder, right_inorder) return root这里需要注意一个细节每次递归时左子树的前序序列长度必须和左子树的中序序列长度相等。所以要先通过中序算出左子树的长度再去前序里切出对应长度的部分。直接拿preorder[1:]当左子树的前序是很多初学者常犯的错误。同理已知后序中序也可以重建树思路一致只是根是后序序列的最后一个元素感兴趣的话可以自己推一遍。3. 旋转实操从 AVL 树到平衡维护的核心环节3.1 什么情况下需要旋转先读懂四种失衡场景旋转不是凭空来的它只在一个特定场景下触发树失衡了。什么叫失衡对二叉搜索树来说通常我们关注每个节点的左右子树高度差。在 AVL 树以发明者 Adelson-Velsky 和 Landis 命名的自平衡二叉搜索树里这个差值绝对值不能超过 1。一旦超过就失衡了需要旋转。失衡场景一共有四种我用最直白的语言描述LL 型某个节点的左子树的左子树太重了。通俗说就是“左左太重”。矫正方法是右旋。RR 型某个节点的右子树的右子树太重了。“右右太重”矫正方法是左旋。LR 型某个节点的左子树的右子树太重了。这是拐弯的形态需要先对左子树做左旋把它变成 LL 型再对根做右旋。RL 型某个节点的右子树的左子树太重了。先对右子树做右旋再对根做左旋。这里我建议你画一张图把四个场景的树形画出来。你会发现一个规律LL 和 RR 是一条直线下来的LR 和 RL 是先折一下的。直线型的只需要一次旋转折线型的需要两次。这比死记硬背强多了。3.2 左旋与右旋代码实现每一步都要画图对照先看右旋。右旋的核心操作是把当前节点的左孩子提上来当新根当前节点变成新根的右孩子新根原来的右孩子过继给当前节点当左孩子。写成代码def right_rotate(y): # 右旋y 是失衡的根节点 x y.left T2 x.right # 旋转 x.right y y.left T2 # 更新高度后面会讲 y.height 1 max(get_height(y.left), get_height(y.right)) x.height 1 max(get_height(x.left), get_height(x.right)) return x左旋就是完全镜像的操作把当前节点的右孩子提上来当新根当前节点变成新根的左孩子新根原来的左孩子过继给当前节点当右孩子def left_rotate(x): y x.right T2 y.left y.left x x.right T2 x.height 1 max(get_height(x.left), get_height(x.right)) y.height 1 max(get_height(y.left), get_height(y.right)) return y这两个函数是整个 AVL 树的发动机。你需要注意旋转完成后一定记得更新参与旋转节点的高度否则后续的平衡因子计算就是错的树的失衡判断也会跟着错。我最早实现 AVL 树时就是漏了高度更新结果插入十几个节点后树就莫名其妙不平衡了。3.3 双旋是怎么组合的LR 与 RL 的完整推导双旋其实不是新的操作就是两次单旋的组合。LR 型即左子树的右子树失衡我们分两步走先对失衡根节点的左孩子做一次左旋此时整棵树变成 LL 型再对失衡根节点做一次右旋。def insert_and_balance(root, key): # 标准 BST 插入 if not root: return TreeNode(key) if key root.val: root.left insert_and_balance(root.left, key) elif key root.val: root.right insert_and_balance(root.right, key) else: return root # 更新高度 root.height 1 max(get_height(root.left), get_height(root.right)) # 计算平衡因子 balance get_balance(root) # LL 型 if balance 1 and key root.left.val: return right_rotate(root) # RR 型 if balance -1 and key root.right.val: return left_rotate(root) # LR 型 if balance 1 and key root.left.val: root.left left_rotate(root.left) return right_rotate(root) # RL 型 if balance -1 and key root.right.val: root.right right_rotate(root.right) return left_rotate(root) return root这里平衡因子的计算方式是左子树高度减去右子树高度。大于 1 说明左边沉了小于 -1 说明右边沉了。为什么还要判断 key 和 root.left.val / root.right.val 的关系因为我们要确定新插入的节点到底是在左子树的左边还是右边以此区分是 LL 还是 LR。这是 AVL 树插入代码最核心的分支判断也是很多人容易写混的地方。3.4 一个模拟插入的完整过程感受平衡因子的变化理论说多了容易飘我直接带你在一个具体序列上走一遍 AVL 树的插入过程。假设依次插入30, 20, 10, 40, 50。插入 30根节点高度 1。插入 2020 小于 30成为左孩子30 的平衡因子变 1没失衡。插入 1010 小于 20成为 20 的左孩子。此时 30 的左子树高度 2右子树高度 0平衡因子 2失衡。判断10 小于 20属于 LL 型对 30 做右旋。旋转后 20 成为根30 成为 20 的右孩子10 保持为 20 的左孩子。插入 4040 大于 20 且大于 30成为 30 的右孩子。此时 20 的右子树高度 2左子树高度 1平衡因子 0没事。插入 5050 大于 30成为 40 的右孩子。此时 30 的平衡因子 -2右子树高度 2左子树高度 0失衡。判断50 大于 40属于 RR 型对 30 做左旋。旋转后 40 成为 20 的右孩子30 成为 40 的左孩子50 保持为 40 的右孩子。你可以在纸上把这棵树画出来感受一下旋转如何通过局部的结构调整让整体高度维持在 log n 的量级。整个过程中中序遍历序列始终是 [10, 20, 30, 40, 50]——旋转没有破坏搜索树的有序性质。这一点是验证旋转是否正确的黄金标准强烈建议你每次写完旋转操作后都用中序遍历检查一次结果。4. 常见问题与排查技巧实录4.1 遍历相关递归栈溢出与迭代死循环遍历最常见的问题有两个。第一个是递归深度过大导致栈溢出这个前面提过了解决办法就是把递归改成显式栈的迭代版本。实际工程里如果你的树是严重偏斜的深度可能达到几十万层递归必定爆栈迭代版本就不会。第二个是迭代中序遍历容易写出死循环。最常见的原因是 while 循环里忘记移动current。我再强调一遍在处理完左子树并弹出节点后一定要把current指向node.right哪怕它是空节点。这样下一轮循环要么从stack继续弹要么从current继续往下走两个条件缺一个都会导致循环无法终止。4.2 旋转相关高度更新遗漏与平衡因子计算混乱旋转出 bug 的高发区第一个就是忘记更新高度。很多初学者在完成节点指针的交换后觉得整个旋转就完事了结果调试时发现平衡因子始终不对。记住只要树的结构变了涉及节点的子树高度就可能变必须在旋转函数内部更新高度。第二个高发区是平衡因子的正负号约定不统一。有的资料用“左减右”有的用“右减左”导致 LL 和 RR 的判断逻辑完全是反的。我的建议是固定用“左子树高度 - 右子树高度”并且固定以大于 1 和小于 -1 作为判断阈值。写代码前先把这个约定写在注释里避免自己把自己绕晕。4.3 定位问题的通用思路用中序遍历做“体检”最后分享一个我这些年调试二叉树问题屡试不爽的万能排查思路。不管你的树看起来多乱只要做两件事第一跑一次中序遍历检查结果是否是有序的。如果无序说明 BST 性质被破坏了问题一定出在插入或旋转时的比较逻辑如果有序说明树结构本身没问题接下来再去查高度和平衡因子的计算。第二写一个递归函数动态计算每个节点的左右子树高度差。如果发现某个节点高度差绝对值大于 1就沿着这个节点的路径找到最低的失衡节点再判断它的孩子节点是哪边高、孙子节点是哪边高从而确定是 LL、RR、LR、RL 中的哪一种照对应的旋转方式修复。这个方法配合调试器使用基本能解决 90% 的二叉树疑难杂症。4.4 一组“深坑”速查表症状大概率原因排查方向中序遍历结果不是升序插入时比较符号写反 / 旋转时把左右子树接错打印插入路径检查每个节点与父节点的比较逻辑前序遍历迭代输出顺序错乱压栈顺序反了应先压右子树再压左子树检查压栈顺序后序遍历结果和递归版本不一致反转前的遍历顺序写得不对先手动模拟一棵三层小树对比节点顺序树的高度越插越大旋转后没有更新节点高度检查 rotate 函数内部是否有 height 更新语句插入后根节点一直不变旋转函数的返回值没有被赋值给插入函数上一层检查递归赋值是否是root.left insert_and_balance(root.left, key)层序遍历各层节点混杂没有在每轮循环开始时固定level_size用len(queue)缓存层大小最后说几句体己话这些东西看着多但真正动手写一遍之后你会发现二叉树没有那么玄。遍历也好旋转也好本质都是对节点指针的重新整理画图比背代码有用十倍。我个人每次写 AVL 树之前都会先在草稿纸上画一棵五节点的树手动模拟一轮插入和旋转再去写代码这个习惯帮我减少了很多不必要的 debug 时间。另外调试二叉树最有力的工具不是打印函数而是可视化树的结构——找一个支持树形输出的调试插件或者自己写一个简单的层序遍历打印比盯着数组结果猜问题快得多。希望这篇笔记能帮你少走一些我当年走过的弯路把遍历和旋转真正变成一个肌肉记忆级别的基本功。
