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

二、二叉树的中序遍历

中序遍历遵循'左子树 → 根节点 → 右子树'的顺序。

1. 递归写法

逻辑非常清晰：先递归左子树，再访问根，最后递归右子树。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        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. 迭代写法

迭代法需要借助栈保存路径上的节点。核心步骤是'一路向左'，直到无法继续，然后回溯访问根节点，再转向右子树。

关键点：

• 外层循环控制整体流程，内层循环负责将左子树节点全部压入栈。
• 弹出栈顶即为当前应访问的根节点。
• 访问后将指针移向右子树。

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

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. 递归写法

依然是最自然的解法：先左，再右，最后根。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        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，来判断当前节点的右子树是否已处理完毕。如果右子树为空或已被访问，说明可以访问当前根节点。

难点： 需要区分'第一次到达该节点'和'左右子树都处理完回到该节点'的状态。

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

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();
            // 如果右子树为空，或者右子树已经访问过（pre 指向它），则可以访问根
            if (node.right == null || pre == node.right) {
                list.add(stack.pop().val);
                pre = node;
                root = null; // 避免重复入栈左子树
            } else {
                // 否则转向右子树
                root = node.right;
            }
        }
        return list;
    }
}

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

这是一个更巧妙的技巧。观察发现：

• 前序遍历：根 → 左 → 右
• 后序遍历：左 → 右 → 根

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

优势： 代码逻辑与前序遍历高度相似，容易记忆。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

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

以上三种遍历方式的递归与迭代实现涵盖了二叉树遍历的核心考点。在实际面试或工程中，建议优先掌握递归写法以理解逻辑，同时熟悉迭代写法以应对栈溢出的极端情况。