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

此方法避免了递归可能导致的栈溢出风险，适合处理深层树结构。

二、二叉树的中序遍历

中序遍历遵循「左子树 → 根节点 → 右子树」的顺序，常用于获取有序序列。

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

迭代的核心在于「一路向左」，直到无法继续，此时栈顶即为当前应访问的根节点。

流程解析：

• 外层循环控制整体进度（栈非空或当前节点不为空）。
• 内层循环持续将左子节点入栈，直到 null。
• 弹出栈顶节点（此时左子树已遍历完），记录值。
• 转向右子节点，重复上述过程。

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

单纯用栈难以区分「首次访问」和「子树处理完毕」。引入 pre 指针记录上一个访问的节点，判断右子树是否已处理。

逻辑要点：

• 若右子树为空或已被访问（pre == node.right），说明左右已完成，可访问根。
• 否则，转向右子树继续遍历。

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. 迭代写法 2：反转前序

观察规律：前序是「根→左→右」，后序是「左→右→根」。若调整为「根→右→左」遍历，结果翻转即得后序。

实现技巧：

• 模仿前序遍历，但入栈顺序改为先左后右（确保右先出栈）。
• 遍历结束后，对结果列表执行 Collections.reverse()。

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

该方案代码简洁，易于记忆，是面试中的高频考点。