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

关键逻辑在于入栈顺序：先右子树、后左子树。这样保证了左子树在右子树之前被访问。该思路避免了递归可能的栈溢出问题，时间复杂度为 O(n)，空间复杂度为 O(n)。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(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();
            if (node == null) continue;
            list.add(node.val);
            stack.push(node.right);
            stack.push(node.left);
        }
        return list;
    }
}

二、二叉树的中序遍历

1. 递归写法

二叉树的中序遍历遵循'左子树——根节点——右子树'的访问顺序。定义函数 inorder(root) 用于返回遍历到 root 节点时的结果。具体执行逻辑为：先递归调用 inorder(root.left)，待左子树遍历完成后，将当前 root 节点的值加入结果集，最后递归调用 inorder(root.right)。当遇到空节点时，递归终止。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
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. 迭代写法

迭代法通过栈存储待访问的节点，利用栈'先进后出'的特性，先深入遍历左子树，再访问根节点，最后处理右子树。

核心逻辑：

1. 初始化：定义列表和栈。若根节点为空，直接返回。
2. 栈循环遍历：外层循环条件为栈非空或仍有节点待处理。内层循环持续将当前节点及其左子树入栈，直到左子树为空。此时栈顶为左子树最深层的节点。弹出栈顶节点，将其值加入列表，然后将指针指向当前节点的右子树。
3. 返回结果：当栈为空且节点指针为空时，遍历结束。

该思路通过迭代高效实现中序遍历，时间复杂度为 O(n)，空间复杂度为 O(n)。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
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(root)，执行逻辑为：先递归调用 postorder(root.left)，再递归调用 postorder(root.right)，待左右子树均遍历完成后，将当前 root 节点的值加入结果集。遇到空节点时递归终止。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
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);
    }
}

迭代写法 1

该代码通过迭代法实现二叉树的后序遍历，核心思路是利用栈模拟递归过程，并通过标记已访问节点解决后序遍历中「左→右→根」的顺序问题。

关键难点：后序遍历的特殊顺序导致单纯用栈难以直接区分「首次访问节点」和「左右子树已处理完毕的节点」。若不标记已访问的右子树，会导致右子树被重复处理或根节点提前访问。

解决方案：

1. 栈的作用：暂存尚未处理完左右子树的节点。
2. 标记已访问节点：用 pre 指针记录上一个被访问的节点，通过判断「当前节点的右子树是否为空或已被访问」，确定是否可以访问当前根节点。

步骤拆解：

1. 初始化：创建结果列表、辅助栈，以及标记上一个访问节点的 pre。
2. 遍历左子树：从当前节点出发，将所有左子树节点依次入栈。
3. 处理栈顶节点：取出栈顶节点，检查其右子树状态。若右子树为空或已被访问，说明左右子树均已处理完毕，此时可以访问根节点。若右子树未访问，则将指针指向右子树，重复步骤 2。
4. 循环终止：当节点为空且栈为空时，返回结果列表。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = 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;
    }
}

迭代写法 2

该代码通过「前序遍历变形 + 列表翻转」的技巧实现二叉树的后序遍历。

关键思路：观察遍历顺序规律，前序遍历为「根→左→右」，后序遍历为「左→右→根」。如果将前序遍历调整为「根→右→左」，得到的结果恰好是后序遍历的逆序。因此，只需按此顺序遍历并记录节点值，最后将列表翻转即可。

步骤拆解：

1. 初始化：创建结果列表和辅助栈。
2. 按「根→右→左」顺序遍历：将根节点入栈，弹出栈顶节点加入列表。若有左子树，将左子树入栈；若有右子树，将右子树入栈。注意入栈顺序应为先左后右，这样右子树会先被弹出访问。
3. 翻转列表：使用 Collections.reverse(list) 翻转列表，得到后序遍历结果。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
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;
    }
}