二叉树前中后序遍历详解：递归与迭代实现

二、二叉树的中序遍历

中序遍历的顺序为：左子树 → 根节点 → 右子树。

1. 递归实现

逻辑与前序类似，区别在于访问当前节点的时机。需先递归完左子树，再记录当前值，最后处理右子树。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        inOrder(root, list);
        return list;
    }

    public void inOrder(TreeNode root, List<Integer> list) {
        if (root == null) return;
        inOrder(root.left, list);
        list.add(root.val);
        inOrder(root.right, list);
    }
}

2. 迭代实现

迭代法需要区分'正在向左深入'和'回溯访问根节点'两个阶段。

核心思路：

• 使用指针 root 不断向左下移动，沿途节点入栈。
• 当无法继续向左时，弹出栈顶节点（此时即为最左侧未访问节点），访问它，然后转向其右子树。
• 重复上述过程直到栈空且 root 为空。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        Deque<TreeNode> stack = new LinkedList<>();
        while (!stack.isEmpty() || root != null) {
            // 一路向左，将路径上的节点入栈
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            // 弹出栈顶，访问根节点
            root = stack.pop();
            list.add(root.val);
            // 转向右子树
            root = root.right;
        }
        return list;
    }
}

三、二叉树的后序遍历

后序遍历的顺序为：左子树 → 右子树 → 根节点。这是最难的一种，因为根节点最后访问，在迭代过程中难以判断何时可以安全地访问根节点。

1. 递归实现

同样遵循'左 - 右 - 根'的递归顺序。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        postOrder(root, list);
        return list;
    }

    public void postOrder(TreeNode root, List<Integer> list) {
        if (root == null) return;
        postOrder(root.left, list);
        postOrder(root.right, list);
        list.add(root.val);
    }
}

2. 迭代实现方案一：标记法

难点在于如何知道右子树已经处理完毕。我们可以引入一个 pre 指针记录上一次被访问的节点。

逻辑解析：

• 遍历到某个节点时，如果它的右子树为空，或者右子树就是上一个访问过的节点（说明右子树已处理完），则可以访问当前节点。
• 否则，先尝试进入右子树。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode node = stack.peek();
            // 若右子树为空或已被访问过，则弹出并记录当前节点
            if (node.right == null || pre == node.right) {
                list.add(stack.pop().val);
                pre = node;
                root = null; // 避免重复入栈左子树
            } else {
                root = node.right;
            }
        }
        return list;
    }
}

3. 迭代实现方案二：前序变形 + 翻转

观察遍历顺序：

• 标准前序：根 → 左 → 右
• 目标后序：左 → 右 → 根

如果我们修改前序遍历的顺序为 根 → 右 → 左，得到的序列正好是后序遍历的逆序。因此，只需按此顺序遍历，最后将结果列表反转即可。

优势： 代码结构与前序遍历高度相似，易于记忆和维护。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            list.add(node.val);
            // 先左后右入栈，保证弹出时是右先左后
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }
        Collections.reverse(list);
        return list;
    }
}

以上三种遍历的时间复杂度均为 O(n)，空间复杂度取决于树的高度，最坏为 O(n)。掌握这些模式有助于应对各类树形结构的算法问题。