二叉树遍历

• 四种方式：

  1. 先序 (PreOrder)：根 → 左 → 右 (DLR)。
  2. 中序 (InOrder)：左 → 根 → 右 (LDR)。
  3. 后序 (PostOrder)：左 → 右 → 根 (LRD)。
  4. 层次遍历 (LevelOrder)：使用 队列 实现。

• 非递归实现 (栈)：

  • 核心是用 栈 模拟递归过程。
  • 难点：后序遍历的非递归（需要记录是否是从右子树返回）。

• 构造二叉树：

  • 先序 + 中序 $\to$ 唯一确定二叉树 (必考大题)。
  • 后序 + 中序 $\to$ 唯一确定二叉树。
  • 注意：先序 + 后序 不能 唯一确定。