二叉树遍历（迭代 + 递归）

递归遍历（三种顺序）

// 前序：根-左-右
void preorder(TreeNode root, List<Integer> res) {
    if (root == null) return;
    res.add(root.val);
    preorder(root.left, res);
    preorder(root.right, res);
}

// 中序：左-根-右（BST 中结果有序）
void inorder(TreeNode root, List<Integer> res) {
    if (root == null) return;
    inorder(root.left, res);
    res.add(root.val);
    inorder(root.right, res);
}

// 后序：左-右-根
void postorder(TreeNode root, List<Integer> res) {
    if (root == null) return;
    postorder(root.left, res);
    postorder(root.right, res);
    res.add(root.val);
}

迭代遍历（用栈模拟）

前序迭代

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    if (root != null) stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        res.add(node.val);
        if (node.right != null) stack.push(node.right); // 先压右（后出）
        if (node.left != null) stack.push(node.left);   // 再压左（先出）
    }
    return res;
}

中序迭代

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    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;
}

后序迭代（前序变形：根左右 → 根右左 → 翻转）

public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> res = new LinkedList<>();  // 头插
    Deque<TreeNode> stack = new ArrayDeque<>();
    if (root != null) stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        res.addFirst(node.val);  // 头插（翻转效果）
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    return res;
}

层序遍历（BFS）

// LeetCode 102
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();  // 当前层的节点数
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        res.add(level);
    }
    return res;
}

层序遍历变体

// LeetCode 107 自底向上层序遍历
// → 正常层序，最后 Collections.reverse(res)

// LeetCode 103 锯齿形层序遍历
// → 用 level 奇偶判断是否头插
boolean leftToRight = true;
for (int i = 0; i < size; i++) {
    TreeNode node = queue.poll();
    if (leftToRight) level.add(node.val);
    else level.addFirst(node.val);    // LinkedList 头插
}
leftToRight = !leftToRight;

莫里斯遍历（O(1) 空间中序）

// 利用叶节点的空指针，不使用栈/递归，空间 O(1)
public List<Integer> morrisInorder(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    TreeNode cur = root, prev;
    while (cur != null) {
        if (cur.left == null) {
            res.add(cur.val);
            cur = cur.right;
        } else {
            prev = cur.left;
            while (prev.right != null && prev.right != cur) prev = prev.right;
            if (prev.right == null) {
                prev.right = cur;   // 建立线索
                cur = cur.left;
            } else {
                prev.right = null;  // 恢复原树
                res.add(cur.val);
                cur = cur.right;
            }
        }
    }
    return res;
}

常见派生问题