树的遍历（递归与迭代）#

前序（根左右）迭代： 栈中弹出访问，先压右再压左 中序（左根右）迭代： 一路向左入栈，弹出访问，转右子 层序（BFS）： 队列逐层出入

高频题： 二叉树最大深度 / 翻转二叉树 / 路径总和 / 最近公共祖先

二叉树遍历分为深度优先和广度优先两大类。深度优先有前序、中序、后序三种，区别在于根节点的访问时机：前序是根左右先处理再递归，中序是左根右先递归左子树再处理根，后序是左右根最后处理根。递归写法非常直观，但面试经常要求迭代写法，核心是用栈模拟递归调用栈。前序迭代最简单：弹出栈顶访问，然后先压右子再压左子，这样左子会先被弹出；中序迭代稍复杂：一路向左把节点全部压栈到底，弹出时访问然后转向右子树继续一路向左。广度优先就是层序遍历，用队列BFS逐层处理，每层开始前记录队列size来区分层次。高频面试题基本都围绕这些遍历展开：二叉树最大深度用递归一行搞定max(左深度,右深度)+1，翻转二叉树递归交换左右子树，最近公共祖先后序遍历自底向上找。如果面试官追问Morris遍历，那是利用叶子节点的空指针做线索实现O(1)空间遍历。

追问方向：

• “前序迭代和递归哪个好？”→ 递归简洁易懂但有 O(n) 栈空间和爆栈风险；迭代用显式栈控制更安全，面试中建议两种都能写，优先展示迭代
• “Morris 遍历了解吗？”→ 利用线索化思想，将空闲的右指针临时指向后继节点，实现 O(1) 空间的中序/前序遍历；遍历结束后恢复树结构，不破坏原树
• “怎么从前序+中序重建二叉树？”→ 前序第一个元素是根，在中序中找到根的位置将序列分为左右子树，递归构建；用 HashMap 缓存中序索引可将查找优化到 O(1)

易错点：

• ❌ 递归一定比迭代慢——差距不大且更简洁
• ❌ 层序遍历只能用队列——可以但队列是标准做法