01

60 秒回答模板

树遍历可以先分 DFS 和 BFS。二叉树 DFS 有前序、 中序、后序：前序是根左右，适合复制树和序列化；中序是左根右，二叉搜索树中序有序；后序是左右根，适合释放资源和自底向上计算。BFS 层序遍历用队列逐层访问。实现上递归最直观，但要注意栈深；迭代可用显式栈或队列。通用多叉树没有固定中序，通常讲前序、后序和层序。

考点 DFS/BFS
难度 真实面经题
回答目标 讲清原理、实现和边界
02

深入解析

01

DFS 和 BFS

深度优先会沿一条路径尽量向下，再回溯访问其他分支；广度优先按层访问节点。两者对应不同的数据结构和应用场景，也是树遍历分类的主线。

02

二叉树三种 DFS

前序是根、左、右；中序是左、根、右；后序是左、右、根。名字描述的是根节点在访问序列中的位置，记住根的位置就不容易混，也方便推导递归模板。

03

层序遍历

层序遍历使用队列，先把根节点入队，每次出队访问并把子节点入队。它适合求层数、最短路径和按层输出，也适合序列化层级结构和宽度统计。

04

递归和迭代

递归代码简洁，但树很深时可能栈溢出；迭代实现使用显式栈或队列，更能控制内存和访问顺序，工程上更可控，也便于处理超深树。

05

不同树的差异

二叉搜索树中序遍历能得到有序序列；多叉树通常没有标准中序，要根据业务定义子节点访问顺序，不能照搬二叉树规则，要先约定孩子访问次序。

03

易错点

  • 不要把前序、中序、后序的根节点位置说反。
  • 不要说所有树都有固定中序，多叉树的中序通常需要额外定义。
  • 不要忽略递归栈空间，深树可能导致栈溢出。
04

面试官追问

如何非递归实现前序遍历？

用栈保存待访问节点，弹出节点后访问，再按右、左顺序入栈，保证左子树先访问。

后序遍历为什么常用于释放资源？

它先处理子节点再处理父节点，符合先释放依赖再释放拥有者的顺序。

二叉搜索树为什么中序有序？

BST 满足左子树小于根、右子树大于根，中序按左根右访问，自然得到升序序列。