元数据卡

• 前置知识：二叉树节点结构、递归思想
• 预计时间：20 分钟
• 完成标志：能写出四种遍历的递归版和迭代版，说清各自复杂度

---

为什么需要遍历

数组有 for 循环——元素按顺序排好了。树的节点之间没有现成的线，你得自己决定"先走哪个分支、后走哪个分支"。

      1
     / \
    2   3
   / \   \
  4   5   6

两个问题：到分叉口先左还是先右？该在什么时候记录当前节点？

---

深度优先：前序 / 中序 / 后序

共用节点：

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

三种递归只有 result.add 的位置不同：

// 前序（根→左→右）：1, 2, 4, 5, 3, 6
void preorder(TreeNode n, List<Integer> r) {
    if (n == null) return;
    r.add(n.val);
    preorder(n.left, r);
    preorder(n.right, r);
}
// 中序（左→根→右）：4, 2, 5, 1, 3, 6
void inorder(TreeNode n, List<Integer> r) {
    if (n == null) return;
    inorder(n.left, r);
    r.add(n.val);
    inorder(n.right, r);
}
// 后序（左→右→根）：4, 5, 2, 6, 3, 1
void postorder(TreeNode n, List<Integer> r) {
    if (n == null) return;
    postorder(n.left, r);
    postorder(n.right, r);
    r.add(n.val);
}

构建并测试：

TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(6);

编译运行：javac *.java && java Main 前序 [1, 2, 4, 5, 3, 6] | 中序 [4, 2, 5, 1, 3, 6] | 后序 [4, 5, 2, 6, 3, 1]

前序用于复制/序列化；中序在 BST 上输出升序；后序用于删除（先删孩子再删父亲）和从底向上求值。

---

迭代版：手动栈代替调用栈

递归简洁，但树深超 ~1000 层会 StackOverflowError。 迭代中序——一路向左压栈，弹出时访问。最经典的栈模拟模式：

List<Integer> inorderIterative(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) { stack.push(cur); cur = cur.left; }
        cur = stack.pop();
        res.add(cur.val);
        cur = cur.right;
    }
    return res;
}

迭代前序——根先入，先右后左压栈保证左先出：

List<Integer> preorderIterative(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode n = stack.pop();
        res.add(n.val);
        if (n.right != null) stack.push(n.right);
        if (n.left != null) stack.push(n.left);
    }
    return res;
}

迭代后序——头插法：以根先出顺序遍历，每次插入到结果头部（反转）：

List<Integer> postorderIterative(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode n = stack.pop();
        res.add(0, n.val);
        if (n.left != null) stack.push(n.left);
        if (n.right != null) stack.push(n.right);
    }
    return res;
}

输出与递归版一致。

---

广度优先：层序遍历

DFS 用栈（深入到底再回头），BFS 用队列（逐层平推）：

List<Integer> levelOrder(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        TreeNode n = q.poll();
        res.add(n.val);
        if (n.left != null) q.offer(n.left);
        if (n.right != null) q.offer(n.right);
    }
    return res;
}

输出 [1, 2, 3, 4, 5, 6]。Java 的 Queue 用 LinkedList 实现，offer/poll 比 add/remove 更安全。

---

复杂度

遍历	结构	空间	时间
DFS 递归	调用栈	O(h)	O(n)
DFS 迭代	手动栈	O(h)	O(n)
BFS 层序	队列	O(n)	O(n)
h 是树高（平衡 log n，退化 n）。全部 O(n)——每个节点访问一次。

---

常见陷阱

1. 忘写 base case：if (n == null) return;——漏了就 NPE。
2. result.add 位置搞混：在前=前序，中=中序，后=后序，三种变体仅差这行。
3. 层序没入队孩子：出队后立即 offer 左右孩子，否则循环只跑一层。
4. Java API 混用：Stack 用 push/pop，Queue 用 offer/poll。

---

通关挑战

热身：对下面 BST 做四种遍历，确认中序结果 [20,30,40,50,60,70,80]：

       50
      /  \
     30   70
    / \   / \
   20 40 60 80

进阶：分组层序——输出 [[50], [30,70], [20,40,60,80]]。提示：int sz = q.size()。

---

旅人笔记

递归版四种遍历只有一行代码的位置变化。迭代版背后是栈（DFS 深入到底）和队列（BFS 逐层平推）的对立——这会在你之后所有的图算法中反复出现。

---

下一站预告

遍历解决"怎么走遍节点"。但 BST 在有序插入下退化为链表，查找从 O(log n) 跌到 O(n)。第 6 章的平衡树——AVL 旋转、红黑树着色——会修复这个缺陷。