二叉树是算法面试的"常青树",递归 + 遍历 + 路径类问题是绝对重点。这篇把模板和经典题整理全。

一、前中后序遍历(递归模板)

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

// 前序:根 → 左 → 右
public void preorder(TreeNode root, List<Integer> res) {
    if (root == null) return;
    res.add(root.val);
    preorder(root.left, res);
    preorder(root.right, res);
}

// 中序:左 → 根 → 右(二叉搜索树中序有序)
public void inorder(TreeNode root, List<Integer> res) {
    if (root == null) return;
    inorder(root.left, res);
    res.add(root.val);
    inorder(root.right, res);
}

// 后序:左 → 右 → 根
public void postorder(TreeNode root, List<Integer> res) {
    if (root == null) return;
    postorder(root.left, res);
    postorder(root.right, res);
    res.add(root.val);
}

递归三要素:终止条件、递推关系、返回值。 终止条件永远是 root == null。

二、层序遍历(BFS 队列模板)

// LeetCode 102 二叉树层序遍历
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();  // 记录当前层节点数
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

关键点:size 必须在循环前记录,否则队列会混入下一层节点。

三、最大深度

// LeetCode 104
public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    return Math.max(left, right) + 1;
}

递归自底向上:先算左右子树深度,再加自己一层。

四、路径总和

// LeetCode 112:是否存在 根到叶子 的和等于 target 的路径
public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    // 到叶子节点判断是否等于目标值
    if (root.left == null && root.right == null) {
        return root.val == targetSum;
    }
    return hasPathSum(root.left, targetSum - root.val)
        || hasPathSum(root.right, targetSum - root.val);
}

技巧:每层把 target 减去当前节点值,到叶子只需判断一次相等。

五、二叉树进阶模板

// 判断是否对称(LeetCode 101)
public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
}

private boolean isMirror(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;
    if (a == null || b == null) return false;
    return a.val == b.val
        && isMirror(a.left, b.right)   // 左对右
        && isMirror(a.right, b.left);  // 右对左
}

// 最近公共祖先(LeetCode 236)
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) return root;  // 一边一个 → 当前是祖先
    return left != null ? left : right;
}

总结

二叉树题永远先想递归:终止条件 + 返回值 + 左右子树合并逻辑。遍历用模板,深度用递归,路径题用"目标值递减"思想。BFS 层序记住 size 先记录。刷熟这几个模板,二叉树面试题 80% 都能直接套。


💡 觉得有用的话,点赞 + 关注【张老师技术栈】吧!

更多推荐