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

解析： 此方法避免了递归的栈溢出风险。实际运行中，入栈顺序决定了出栈顺序，务必记住'右先左后'这一细节。

二、二叉树的中序遍历

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. 迭代写法

迭代的核心在于'一路向左'，直到无法继续，然后回溯访问根节点，再转向右子树。

核心逻辑：

1. 使用指针 curr 指向当前节点。
2. 只要 curr 不为空或栈非空：
   • 若 curr 不为空，将其压栈并向左移动。
   • 若 curr 为空，说明左侧已到底，弹出栈顶（即最近的一个祖先），访问它，然后转向其右子树。

代码实现：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            list.add(curr.val);
            curr = curr.right;
        }
        return list;
    }
}

三、二叉树的后序遍历

后序遍历顺序为'左子树 → 右子树 → 根节点'。这是三种遍历中最难用迭代实现的，因为根节点最后访问，需要区分何时可以安全地访问根节点。

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. 迭代写法 1：双指针标记法

通过记录上一个访问的节点 pre，判断当前节点的右子树是否已处理完毕。

核心逻辑：

1. 遍历到最左节点入栈。
2. 检查栈顶节点的右子树：如果为空或已被访问过，则弹出并访问当前节点；否则转向右子树。

代码实现：

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 || node.right == pre) {
                list.add(stack.pop().val);
                pre = node;
                root = null;
            } else {
                root = node.right;
            }
        }
        return list;
    }
}

3. 迭代写法 2：前序变形 + 翻转

利用前序遍历'根→左→右'与后序遍历'左→右→根'的关系。如果我们修改前序遍历为'根→右→左'，得到的结果反转后即为后序遍历。

核心逻辑：

1. 按'根→右→左'顺序遍历（先入右子树，再入左子树）。
2. 遍历结束后，将结果列表反转。

代码实现：

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

总结：

• 递归写法代码量少，易于理解，但受限于系统栈深度。
• 迭代写法更稳健，适合对性能要求高或树结构极深的场景。
• 后序遍历的迭代实现中，'翻转法'通常比'双指针法'更易编写且不易出错。