二叉树遍历学习手册

二叉树遍历学习手册 目录1. 适用场景2. 核心原理2.1 一句话口诀2.2 代码位置决定遍历顺序2.3 三种遍历对比表3. 具体做法3.1 递归模板DFS3.2 迭代模板栈模拟4. 实战案例判断两棵树是否相同4.1 问题描述4.2 错误示范 为什么它能跑对4.3 标准解法5. 安全锁清单5.1 null 到了边界为什么还要往下走5.2 Python 的 and 短路会跳过另一半对比吗5.3 递归写法有哪些常见坑6. 进阶方向1. 适用场景二叉树遍历是几乎所有树相关问题的基础操作。你在以下场景中一定需要掌握遍历顺序场景推荐遍历原因二叉搜索树BST升序输出中序中序遍历 BST 有序序列序列化 / 反序列化树前序根在前方便重建树结构计算树的高度 / 后序清理后序先处理子树再处理根层序打印 / 最短路径层序BFS按层遍历非本文范围判断两棵树是否相同前序同步对比根→左→右同步推进什么时候不用操心顺序如果问题只关心遍历所有节点不关心处理顺序如累加所有节点值前/中/后序都可以。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 A2.3 三种遍历对比表遍历方式口诀根的位置典型应用一句话记忆法前序 Pre-order根左右最先序列化、复制树先处理自己再处理孩子中序 In-order左根右中间BST 升序遍历左子树搞定再打印自己后序 Post-order左右根最后删除树、后序依赖计算孩子都处理完再处理自己3. 具体做法3.1 递归模板DFS三种遍历在递归中的区别仅仅是print的位置不同框架完全一致classTreeNode:def__init__(self,val0,leftNone,rightNone):self.valval self.leftleft self.rightrightdeftraverse(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)returnresult3.2 迭代模板栈模拟递归的本质是系统栈手动用栈模拟就是迭代遍历。前序最直观根先入栈每次弹出处理然后先右后左入栈栈后进先出要保证左先处理defpreorder(root:TreeNode)-List[int]:ifnotroot:return[]stack,result[root],[]whilestack:nodestack.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[],[]currrootwhilecurrorstack:whilecurr:# 一路向左压入所有左子节点stack.append(curr)currcurr.left currstack.pop()# 弹出最左节点result.append(curr.val)# 打印左→根currcurr.right# 转向右子树returnresult后序技巧前序变体 反转前序是根左右改成根右左再反转结果就是左右根defpostorder(root:TreeNode)-List[int]:ifnotroot:return[]stack,result[root],[]whilestack:nodestack.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)这段代码是正确的。四个分支各自的执行路径条件结果是否走到递归调用都非空但值不等return False❌ 提前返回都非空且值相等不进入任何分支的 return✅执行递归一个空一个不空return False❌ 提前返回两个都空return True❌ 提前返回为什么需要第 33 行的递归调用它承担了两个角色向下钻— 当前节点相等继续对比左右子树是否也相等向上传— 子树的比对结果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 层p1, q1 值相等 → 走递归调用 └── dfs_compare(left) ← 先算 and 的左操作数 第 2 层p2, q2 值相等 → 走递归调用 ├── dfs_compare(左) ← 先算 and 的左操作数 │ 第 3 层null, null → else: return True ✅ └── dfs_compare(右) ← 再算 and 的右操作数 第 3 层p4, qnull → 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)代码逻辑映射情景条件返回值含义Anot p and not qTrue同时越过了叶子节点Bnot p or not qFalse结构不对称Cp.val ! q.valFalse值不同D以上都不满足递归对比左右继续下钻这套写法的优势只有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 递归写法有哪些常见坑坑现象正确做法if not p and not q之后忘了return递归进入 null 节点的左右孩子 →AttributeError一定要在条件分支里returnnot p or not q写在p.val判断之前空指针访问 → 崩溃先判空再取值p.val ! q.val写成p.val ! q.val and ...再加递归逻辑混乱值不等直接return False在if分支外写递归死代码永远不会执行如 4.2 的错误示范递归直接写在return里6. 进阶方向本文范围之外的扩展内容方向简介难度层序遍历BFS 队列实现按层输出节点⭐Morris 遍历O(1) 空间复杂度的遍历利用线索二叉树⭐⭐⭐N 叉树遍历前/后序推广到多叉树⭐遍历 回溯在遍历过程中记录路径如路径总和问题⭐⭐多树遍历对比同时遍历两棵树如 Same Tree、Subtree⭐⭐一句话总结前中后序的区别 print写在递归三兄弟左 / 根 / 右的哪个位置。