二叉树遍历其实就是在树上“摸球”别再死记硬背“根左右”了用手指绕着树走一圈什么都清楚了一个让初学者崩溃的问题学数据结构的时候二叉树遍历大概是很多人第一次感到“我好像懂了但一做题就错”的地方。前序遍历根左右。中序遍历左根右。后序遍历左右根。口诀背得滚瓜烂熟可一遇到下面这棵树A / \ B C / \ \ D E F问你后序遍历是什么你开始默念“左右根……左右根……”先写D再写E然后B……不对F和C什么时候写A放在哪里脑子里的递归栈像一团乱麻捋不清。其实不是你笨而是这个方法本身就反直觉。今天我们换一种方式来看遍历。保证你看完之后再也不会搞混前序、中序和后序。把树想象成一座过山车轨道我们先做一个小小的思维实验。请你把上面那棵二叉树想象成一座过山车的轨道。节点A、B、C、D、E、F就是轨道的支柱树枝就是连接支柱的轨道。现在我们要做一件非常简单的事从根节点A的左边出发贴着轨道的外侧逆时针走一圈回到原点。就这么简单。你不需要思考任何递归逻辑只需要像小孩画圈一样沿着树的边缘走一圈。为了帮助理解我们先在每个节点的左侧、正下方、右侧分别画上一个小球A / \ B C / \ \ D E F 红色球 节点左侧绿色球 节点正下方蓝色球 节点右侧三种遍历说白了就是三种不同的摸球规则遍历方式摸什么颜色的球通俗说法前序遍历 只摸红色球只摸左边的球中序遍历 只摸绿色球只摸下边的球后序遍历 只摸蓝色球只摸右边的球第一圈前序遍历 —— 只摸红色球伸出你的食指放在A的左边开始沿着树的边缘逆时针滑动。这一圈你只盯着红色的球。手指经过红色球时就记录其他颜色一概忽略。我们来走一遍从A左边出发 → 摸到A的红色球往下走到B左边 → 摸到B的红色球继续下到D左边 → 摸到D的红色球绕过D底部绿色球忽略绕到D右边蓝色球忽略回到B从B往右下走到E左边 → 摸到E的红色球绕过E回到B回到A从A往右下走到C左边 → 摸到C的红色球继续走到F左边 → 摸到F的红色球你摸到的红色球顺序是A → B → D → E → C → F这就是前序遍历。第二圈中序遍历 —— 只摸绿色球再走一圈还是那条路从A左边出发逆时针绕行。这一圈你只盯着绿色的球。经过A左边红色忽略到B左边红色忽略到D左边红色忽略绕到D底部 → 摸到D的绿色球回到B底部 → 摸到B的绿色球到E底部 → 摸到E的绿色球回到A底部注意A的绿色球在B和C轨道交叉点的正下方→ 摸到A的绿色球到C底部 → 摸到C的绿色球到F底部 → 摸到F的绿色球你摸到的绿色球顺序是D → B → E → A → C → F这就是中序遍历。第三圈后序遍历 —— 只摸蓝色球再走最后一圈。这一圈你只盯着蓝色的球。注意根节点A的蓝色球在整棵树的最高点右侧要到最后时刻才会被摸到。深入左子树绕到D右侧 → 摸到D的蓝色球回到B右侧 → 摸到B的蓝色球到E右侧 → 摸到E的蓝色球回到A不急着摸A还没绕到继续进入C子树先到F右侧 → 摸到F的蓝色球回到C右侧 → 摸到C的蓝色球最后绕到A右侧顶端 → 摸到A的蓝色球你摸到的蓝色球顺序是D → E → B → F → C → A这就是后序遍历。三张图对比一目了然遍历方式摸球颜色摸球位置结果序列前序 红色摸左边A → B → D → E → C → F中序 绿色摸下边D → B → E → A → C → F后序 蓝色摸右边D → E → B → F → C → A口诀只有一句话前红、中绿、后蓝。不用再背“根左右”了。代码验证让计算机替我们走一圈理解了“摸球法”之后我们再来看代码。你会发现递归代码本质上就是在模拟这“绕圈走”的过程。二叉树的节点定义PythonclassTreeNode:def__init__(self,val):self.valval self.leftNoneself.rightNone构建我们示例中的那棵树# 构建示例树# A# / \# B C# / \ \# D E FATreeNode(A)BTreeNode(B)CTreeNode(C)DTreeNode(D)ETreeNode(E)FTreeNode(F)A.leftB A.rightC B.leftD B.rightE C.rightF三种遍历的递归代码defpreorder(root):前序遍历根 - 左 - 右ifrootisNone:return[]return[root.val]preorder(root.left)preorder(root.right)definorder(root):中序遍历左 - 根 - 右ifrootisNone:return[]returninorder(root.left)[root.val]inorder(root.right)defpostorder(root):后序遍历左 - 右 - 根ifrootisNone:return[]returnpostorder(root.left)postorder(root.right)[root.val]# 运行验证print(前序遍历,preorder(A))# [A, B, D, E, C, F]print(中序遍历,inorder(A))# [D, B, E, A, C, F]print(后序遍历,postorder(A))# [D, E, B, F, C, A]把摸球法的注释写在代码里defpreorder(root):前序遍历 摸红色球左侧球ifrootisNone:return[]# 离开当前节点之前先摸左侧红球return[root.val]preorder(root.left)preorder(root.right)definorder(root):中序遍历 摸绿色球正下方球ifrootisNone:return[]left_resultinorder(root.left)# 从左子树回来到达节点正下方摸绿色球returnleft_result[root.val]inorder(root.right)defpostorder(root):后序遍历 摸蓝色球右侧球ifrootisNone:return[]left_resultpostorder(root.left)right_resultpostorder(root.right)# 左右子树都处理完了绕到节点右侧摸蓝色球returnleft_resultright_result[root.val]这段注释清晰地标出了递归代码中的访问时机正好对应了绕圈过程中碰到红、绿、蓝球的时刻。迭代版代码模拟绕圈的过程递归代码简洁但“摸球法”的本质其实是沿着树的边缘走一圈。用迭代的方式写出来更能体现这种“绕圈”的感觉defpreorder_iterative(root):前序遍历迭代版模拟沿着树边缘走优先摸左侧红球ifnotroot:return[]result[]stack[root]whilestack:nodestack.pop()result.append(node.val)# 摸到红球# 注意栈是后进先出所以先压右孩子再压左孩子ifnode.right:stack.append(node.right)ifnode.left:stack.append(node.left)returnresultdefinorder_iterative(root):中序遍历迭代版先深入左下再摸绿球result[]stack[]currootwhilestackorcur:# 一路向左把经过的节点压栈whilecur:stack.append(cur)curcur.left# 到达最左下弹出节点摸绿色球curstack.pop()result.append(cur.val)# 转向右子树curcur.rightreturnresultdefpostorder_iterative(root):后序遍历迭代版最后摸蓝色球ifnotroot:return[]result[]stack[root]whilestack:nodestack.pop()result.append(node.val)ifnode.left:stack.append(node.left)ifnode.right:stack.append(node.right)# 反转得到正确顺序左右根returnresult[::-1]# 验证print(前序迭代,preorder_iterative(A))print(中序迭代,inorder_iterative(A))print(后序迭代,postorder_iterative(A))为什么“摸球法”比背口诀好对比维度传统口诀法根左右/左根右/左右根摸球法红绿蓝记忆方式背三组不同的顺序只记“红绿蓝”三个颜色出错概率容易搞混根的位置手指沿轨道走绝不会漏理解深度停留在口诀层面直观理解遍历的几何本质与代码对应需要额外映射红先输出绿中间输出蓝最后输出适用人群需要一定抽象思维小学生都能看懂总结二叉树的三种遍历本质上是同一条路径上的三次“经过”第一次经过节点时访问 → 前序摸红球第二次经过节点时访问 → 中序摸绿球第三次经过节点时访问 → 后序摸蓝球(第1次经过) | A(第3次经过) (第2次经过)这就是为什么递归代码只需要调换三行代码的顺序就能实现三种不同的遍历。因为它们本来就是同一套逻辑只是访问的时机不同而已。下次有人问你二叉树遍历别急着背口诀。拿出笔画一棵树在每个节点旁边画上红、绿、蓝三个小球然后伸出手指沿着树的边缘走一圈。前序摸红中序摸绿后序摸蓝。就这么简单。