二叉树遍历：递归、迭代与层序

// 前序遍历：根 → 左 → 右
public void preorder(TreeNode cur, List<Integer> res) {
    if (cur == null) return;        // 终止条件：走到空
    res.add(cur.val);               // ① 访问根
    preorder(cur.left, res);        // ② 递归左子树
    preorder(cur.right, res);       // ③ 递归右子树
}
// 中序：②①③ 交换两行位置；后序：②③① 再交换

// 统一迭代：中序遍历，前序/后序只改标记和孩子的入栈顺序
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    if (root != null) stack.push(root);
 
    while (!stack.isEmpty()) {
        TreeNode node = stack.peek();
        if (node != null) {
            stack.pop();                     // 先把节点弹掉，再按序安排
            if (node.right != null) stack.push(node.right); // 中序：右最后
            stack.push(node);                // 节点自己重新入栈
            stack.push(null);                // null 标记：下次见到就访问
            if (node.left != null) stack.push(node.left);   // 中序：左最先
        } else {
            stack.pop();                     // 弹出 null 标记
            TreeNode cur = stack.pop();      // 紧随其后的节点正是该访问的
            res.add(cur.val);                // 此处是唯一的"访问"动作
        }
    }
    return res;
}

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;            // 空树直接返回，别让 null 进队
 
    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);                       // 根节点作为第 1 层唯一成员
 
    while (!queue.isEmpty()) {
        int size = queue.size();             // 固定！此时队列里恰好是整层节点
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {     // 只处理 size 个，不碰刚入队的下一层
            TreeNode cur = queue.poll();     // 队头出队
            level.add(cur.val);              // 收集本层节点值
            if (cur.left != null) queue.offer(cur.left);   // 左孩子进下一层
            if (cur.right != null) queue.offer(cur.right); // 右孩子进下一层
        }
        res.add(level);                      // 本层完成，挂到结果上
    }
    return res;
}