二叉树遍历学习手册

二叉树遍历学习手册

📖 目录

• 1. 适用场景
• 2. 核心原理
  • 2.1 一句话口诀
  • 2.2 代码位置决定遍历顺序
  • 2.3 三种遍历对比表
• 3. 具体做法
  • 3.1 递归模板（DFS）
  • 3.2 迭代模板（栈模拟）
• 4. 实战案例：判断两棵树是否相同
  • 4.1 问题描述
  • 4.2 错误示范 & 为什么它能跑对
  • 4.3 标准解法
• 5. 安全锁清单
  • 5.1 null 到了边界，为什么还要往下走？
  • 5.2 Python 的 and 短路会跳过另一半对比吗？
  • 5.3 递归写法有哪些常见坑？
• 6. 进阶方向

1. 适用场景

二叉树遍历是几乎所有树相关问题的基础操作。你在以下场景中一定需要掌握遍历顺序：

什么时候不用操心顺序？如果问题只关心"遍历所有节点"，不关心处理顺序（如累加所有节点值），前/中/后序都可以。

2. 核心原理

2.1 一句话口诀

前序（Pre-order）： 根 左 右 —— 根最先打印，进门先拜祖宗 中序（In-order）： 左 根 右 —— 根在中间打印，左子树干完再打印自己 后序（Post-order）： 左 右 根 —— 根最后打印，儿孙都处理完了再处理自己

假设永远先左后右，只需要盯住根节点（Root）何时被访问。

2.2 代码位置决定遍历顺序

在同一个递归函数里，print写在三个不同位置，就产生三种顺序：

defdfs(node):ifnodeisNone:return# 【位置 1】print 写在这里 → 前序（根左右）print(node.val)dfs(node.left)# 【位置 2】print 写在这里 → 中序（左根右）print(node.val)dfs(node.right)# 【位置 3】print 写在这里 → 后序（左右根）print(node.val)

在一棵只有 3 个节点的树上（根 A，左 B，右 C），三种遍历结果：

前序：A B C 中序：B A C 后序：B C A

扩展到多节点树，同样的规律递归地应用到每个子树：

A / \ B C / \ / \ D E F G 前序：A B D E C F G 中序：D B E A F C G 后序：D E B F G C A

2.3 三种遍历对比表

3. 具体做法

3.1 递归模板（DFS）

三种遍历在递归中的区别仅仅是print的位置不同，框架完全一致：

classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=val self.left=left self.right=rightdeftraverse(root:TreeNode)->List[int]:"""前/中/后序模板：移动 print 位置即可切换"""result=[]defdfs(node):ifnodeisNone:return# 【前序】result.append(node.val)dfs(node.left)# 【中序】result.append(node.val)dfs(node.right)# 【后序】result.append(node.val)dfs(root)returnresult

3.2 迭代模板（栈模拟）

递归的本质是系统栈，手动用栈模拟就是迭代遍历。

前序（最直观）

根先入栈，每次弹出处理，然后先右后左入栈（栈后进先出，要保证左先处理）：

defpreorder(root:TreeNode)->List[int]:ifnotroot:return[]stack,result=[root],[]whilestack:node=stack.pop()result.append(node.val)ifnode.right:# 右先入栈，左后入栈stack.append(node.right)# 这样左先出栈，满足「根左右」ifnode.left:stack.append(node.left)returnresult

中序（最需要理解）

指针一路向左到底，回溯时打印，然后转向右子树：

definorder(root:TreeNode)->List[int]:stack,result=[],[]curr=rootwhilecurrorstack:whilecurr:# 一路向左，压入所有左子节点stack.append(curr)curr=curr.left curr=stack.pop()# 弹出最左节点result.append(curr.val)# 打印（左→根）curr=curr.right# 转向右子树returnresult

后序（技巧：前序变体 + 反转）

前序是根左右，改成根右左，再反转结果就是左右根：

defpostorder(root:TreeNode)->List[int]:ifnotroot:return[]stack,result=[root],[]whilestack:node=stack.pop()result.append(node.val)# 根先ifnode.left:# 左后入栈（和「前序」入栈顺序相反）stack.append(node.left)# 右先出栈 → 顺序为根右左ifnode.right:stack.append(node.right)returnresult[::-1]# 反转 → 左右根

三种迭代对比

4. 实战案例：判断两棵树是否相同

4.1 问题描述

LeetCode 100. Same Tree

给定两棵二叉树的根节点p和q，判断它们是否完全相同（结构相同 + 节点值相同）。

4.2 一种分步写法（便于理解递归传递过程）

先看一个写法，它把「空值判断」和「值判断」拆成了三个独立分支：

classSolution:defisSameTree(self,p:Optional[TreeNode],q:Optional[TreeNode])->bool:defdfs_compare(check_node,compare_node):ifcheck_nodeandcompare_node:ifcheck_node.val!=compare_node.val:returnFalseelif(check_nodeandnotcompare_node)or(notcheck_nodeandcompare_node):returnFalseelse:returnTrue# 👇 两个节点都非空 且 值相等时，走到这里继续递归returndfs_compare(check_node.left,compare_node.left)and\ dfs_compare(check_node.right,compare_node.right)returndfs_compare(p,q)

这段代码是正确的。四个分支各自的执行路径：

为什么需要第 33 行的递归调用？它承担了两个角色：

1. 向下钻— 当前节点相等，继续对比左右子树是否也相等
2. 向上传— 子树的比对结果（True 或 False）通过return逐层传回最外层

没有这行的话，函数只能对比根节点，深层的不匹配传不回来。

用p = [1,2,3,null,4,5,null]和q = [1,2,3,null,null,6,null]跑一遍，看看递归是怎么传递结果的：

树 p 树 q 1 1 / \ / \ 2 3 2 3 \ / / / 4 5 null 6

递归执行过程（关键帧）：

第 1 层：p=1, q=1 值相等 → 走递归调用 └── dfs_compare(left) ← 先算 and 的左操作数 第 2 层：p=2, q=2 值相等 → 走递归调用 ├── dfs_compare(左) ← 先算 and 的左操作数 │ 第 3 层：null, null → else: return True ✅ └── dfs_compare(右) ← 再算 and 的右操作数 第 3 层：p=4, q=null → elif: return False ⚡ 第 2 层：return True and False → return False 第 1 层收到左边 False → Python 短路 and，跳过右边，直接 return False

判定为 false 的关键：p的节点2有右孩子4，但q的节点2没有右孩子（null）—— 结构不对称在第 3 层被揪出来，靠return dfs_compare(...)一路传回最外层。

4.3 标准解法

classSolution:defisSameTree(self,p:Optional[TreeNode],q:Optional[TreeNode])->bool:# 【情景1】两个都空 → 到底了，相同ifnotpandnotq:returnTrue# 【情景2】其中一个空 / 值不等 → 不同ifnotpornotqorp.val!=q.val:returnFalse# 【情景3】递归对比左右子树，必须都 Truereturnself.isSameTree(p.left,q.left)andself.isSameTree(p.right,q.right)

代码逻辑映射：

这套写法的优势：

• 只有3 个分支，没有多余代码
• 递归调用在return里直接返回，不会产生死代码
• and短路恰好表达"左右子树必须都相同"

5. 安全锁清单

5.1 null 到了边界，为什么还要往下走？

初学者常有的困惑：“null不是到底了吗？为什么还会有False返回？”

关键理解：null只代表"当前这一条路"走到头了，父节点还有另一条路要对比。

2 ← 父节点 / \ null 4 ← 右孩子还没对比呢！

递归不是一条直线，而是一个分叉。一个分支到边界后，函数回溯到父节点，父节点会继续走另一个分支。

5.2 Python 的 and 短路会跳过另一半对比吗？

会，但这正是我们想要的。

returnself.isSameTree(p.left,q.left)andself.isSameTree(p.right,q.right)

• 如果左子树已经返回False（结构不同），右子树根本不会执行
• 这是性能优化，不是 bug——左子树不同，整棵树必然不同

5.3 递归写法有哪些常见坑？

6. 进阶方向

本文范围之外的扩展内容：

一句话总结：前中后序的区别 =print写在递归三兄弟（左 / 根 / 右）的哪个位置。