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

二、中序遍历 (Inorder)

中序遍历的顺序是：左子树 → 根节点 → 右子树。这在二叉搜索树（BST）中能获取有序序列。

1. 递归实现

逻辑非常清晰：先钻到最左边，回溯时访问根，最后去右边。

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

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

2. 迭代实现

迭代的中序遍历稍微复杂一点。我们需要一个指针不断向左走，把路径上的节点都压栈。直到没有左孩子了，弹出栈顶（这就是当前层级的根），然后转向右子树。

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;
    }
}

三、后序遍历 (Postorder)

后序遍历的顺序是：左子树 → 右子树 → 根节点。难点在于根节点最后访问，迭代时需要判断何时可以安全地访问根节点。

1. 递归实现

依然是最简洁的方式：左 -> 右 -> 根。

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

    private 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)。