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

二叉树前中后序遍历详解

一、二叉树的前序遍历

1. 递归写法

前序遍历的核心规则是'根节点 → 左子树 → 右子树'。递归实现最直观，直接按照定义编写即可。

核心思路 先访问当前节点的值，再递归处理左子树，最后递归处理右子树。当遇到空节点时停止。

代码实现

/**
 * 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 {
    private List<Integer> list = new ArrayList<>();

    public List<Integer> preorderTraversal(TreeNode root) {
        find(root);
        return list;
    }

    private void find(TreeNode node) {
        if (node != null) {
            list.add(node.val);
            find(node.left);
            find(node.right);
        }
    }
}

解析 时间复杂度 O(n)，每个节点访问一次。空间复杂度 O(n)，主要消耗在递归栈和结果列表上。这种方式代码简洁，但需注意递归深度过大可能导致栈溢出。

2. 迭代写法

迭代法利用栈来模拟递归调用过程。关键在于入栈顺序：为了保证'左子树'先于'右子树'被访问，我们需要将右子树先入栈，左子树后入栈。

核心逻辑

1. 初始化栈，将根节点压入。
2. 循环弹出栈顶节点并访问。
3. 先将右子节点入栈，再将左子节点入栈（后进先出，确保左先出）。

代码实现

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);
            // 注意顺序：先右后左
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
        return list;
    }
}

解析 这种方法避免了递归的栈溢出风险。逻辑上完全等价于递归，只是显式地管理了调用栈。

二、二叉树的中序遍历

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

迭代中序遍历稍微复杂一些，需要用到一个指针 root 和一个栈 stack。

核心思路

1. 只要还有节点没处理（root != null）或者栈里还有节点（!stack.isEmpty()），就继续循环。
2. 一路向左：不断将当前节点及其左子节点入栈，直到 root 为空。这保证了最左侧的节点最先被处理。
3. 访问根节点：弹出栈顶元素，此时该元素的左子树已遍历完毕，可以安全访问它。
4. 转向右子树：将 root 指向弹出节点的右孩子，重复上述过程。

代码实现

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，用来判断右子树是否已经处理完毕。

关键逻辑

• 如果当前节点的右子树为空，或者右子树就是上一个访问的节点，说明左右子树都处理完了，可以访问当前节点。
• 否则，尝试进入右子树。

代码实现

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：前序翻转法

这是一个巧妙的技巧。观察顺序：

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

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

步骤拆解

1. 模仿前序遍历，但入栈顺序改为：先左后右（因为栈是后进先出，为了先访问右，需后入栈右？不对，为了先访问右，需先入栈左，后入栈右，这样右先出栈）。修正：为了得到'根→右→左'，弹出根后，应先将左入栈，再将右入栈。这样右先出栈。
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;
    }
}

总结 三种遍历方式中，递归写法最为直观，适合理解原理；迭代写法在实际工程中更稳健，能避免深层递归导致的栈溢出问题。特别是后序遍历的两种迭代解法，掌握其背后的逻辑（标记法 vs 翻转法）对提升算法思维很有帮助。