二叉树遍历模板：前中后序、层序与递归迭代一套拿下#

二叉树题目的入口往往不是某个复杂算法，而是先把遍历写稳。只要遍历稳了，很多题其实就是“在遍历过程中做一点事”。

⚡ 速记版模板#

// 模板用途：标准递归遍历骨架，可替换“处理当前节点”位置得到前/中/后序
void dfs(TreeNode node) {
    if (node == null) { // 递归终止条件：空节点直接返回
        return;
    }
    dfs(node.left); // 先递归左子树
    处理当前节点; // 在中间位置处理当前节点（这是中序遍历位置）
    dfs(node.right); // 再递归右子树
}

java

🎯 什么时候先写遍历模板？#

几乎所有二叉树题都离不开遍历：

中序遍历
最大深度
翻转二叉树
对称二叉树
层序遍历
验证 BST
最近公共祖先
路径总和

Hot 100 里的典型题目：

💡 递归三要素#

写树的递归时，先想清楚三件事：

函数参数和返回值是什么
终止条件是什么
当前节点要做什么

🚀 模板一：前序遍历#

顺序：根 -> 左 -> 右

class Solution {
    List<Integer> result = new ArrayList<>(); // 保存前序遍历结果

    public List<Integer> preorderTraversal(TreeNode root) {
        traverse(root); // 从根节点开始 DFS
        return result; // 返回“根-左-右”顺序结果
    }

    private void traverse(TreeNode node) {
        if (node == null) { // 终止条件：空节点
            return;
        }

        result.add(node.val); // 前序位置：先处理当前根节点
        traverse(node.left); // 再递归左子树
        traverse(node.right); // 最后递归右子树
    }
}

java

适合：

复制树结构
构造路径
展开树

🚀 模板二：中序遍历#

顺序：左 -> 根 -> 右

class Solution {
    List<Integer> result = new ArrayList<>(); // 保存中序遍历结果

    public List<Integer> inorderTraversal(TreeNode root) {
        traverse(root); // 从根节点开始递归
        return result; // 返回“左-根-右”结果
    }

    private void traverse(TreeNode node) {
        if (node == null) { // 空节点终止
            return;
        }

        traverse(node.left); // 先访问左子树
        result.add(node.val); // 中序位置处理当前节点
        traverse(node.right); // 再访问右子树
    }
}

java

适合：

BST 相关题目
验证是否有序
第 K 小元素

🚀 模板三：后序遍历#

顺序：左 -> 右 -> 根

class Solution {
    private int dfs(TreeNode node) {
        if (node == null) { // 空树高度为 0
            return 0;
        }

        int left = dfs(node.left); // 先求左子树高度
        int right = dfs(node.right); // 再求右子树高度

        return Math.max(left, right) + 1; // 当前节点高度 = 子树最大高度 + 1（后序汇总）
    }
}

java

适合：

高度计算
路径和
子树信息汇总

很多“先算左右子树，再决定当前节点答案”的题，都偏向后序。

🚀 模板四：层序遍历#

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>(); // 保存每一层的节点值
        if (root == null) { // 边界：空树直接返回空结果
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>(); // BFS 队列
        queue.offer(root); // 根节点入队作为第 0 层起点

        while (!queue.isEmpty()) { // 逐层遍历
            int size = queue.size(); // 当前层节点数量
            List<Integer> level = new ArrayList<>(); // 存当前层值

            for (int count = 0; count < size; count++) { // 精确处理当前层
                TreeNode current = queue.poll(); // 取出本层一个节点
                level.add(current.val); // 记录节点值

                if (current.left != null) { // 左子节点非空则加入下一层
                    queue.offer(current.left);
                }
                if (current.right != null) { // 右子节点非空则加入下一层
                    queue.offer(current.right);
                }
            }

            result.add(level); // 当前层处理完，加入总结果
        }

        return result; // 返回层序遍历结果
    }
}

java

适合：

层序遍历
右视图
每层统计信息

🚀 模板五：迭代中序遍历#

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>(); // 保存中序结果
        Deque<TreeNode> stack = new ArrayDeque<>(); // 显式栈，模拟递归调用栈
        TreeNode current = root; // 当前遍历指针

        while (current != null || !stack.isEmpty()) { // 还有未处理节点时继续
            while (current != null) { // 一路向左，把沿途节点压栈
                stack.push(current);
                current = current.left;
            }

            current = stack.pop(); // 左链走到底后，弹出栈顶（最左未处理节点）
            result.add(current.val); // 处理中序“根”位置
            current = current.right; // 转向右子树，重复同样过程
        }

        return result; // 返回迭代中序结果
    }
}

java

🧠 常见题目怎么套？#

1. 最大深度#

后序递归：左右子树高度取最大

2. 翻转二叉树#

前序或后序都可以
在递归过程中交换左右孩子

3. 验证二叉搜索树#

中序遍历结果必须严格递增

4. 最近公共祖先#

后序思路更自然
左右子树返回结果后再判断当前节点

⚠️ 易错点#

把遍历顺序想错
- 先想清楚题目需要“先处理当前节点”还是“先拿到子树结果”
递归返回值和全局变量混用混乱
- 计数类、路径类题目尤其容易乱
层序遍历忘记按层处理
- 要先记录 size
BST 题目误以为任意遍历都行
- BST 的天然顺序是中序

🎨 面试时怎么说#

你可以这样说：

我先判断这题更适合哪种遍历顺序。如果题目依赖左右子树结果，就优先后序；如果是 BST 的顺序性质，就优先中序；如果题目按层处理，就用 BFS 层序遍历。

📌 一句话总结#

二叉树题目先别急着想花活，先问自己：

这题最自然的遍历顺序是什么？
当前节点的答案是否依赖左右子树？

把这两件事想明白，大部分树题就开了。