程序员面试手册
程序员面试手册

Appearance

Star

二叉树 ​

数据结构 ⭐⭐ 中级 🔥 高频

💡 核心要点

二叉树面试题的核心是递归思维。90% 的二叉树题可以归结为一个问题：对于当前节点，我需要从左右子树获取什么信息，然后如何组合出答案？

识别信号 ​

拿到题目时，先看题目描述属于哪类信号，快速锁定解法：

题目信号推荐方法原因
"逐层处理" / "最短距离" / "每层的…"BFS 层序队列天然按层展开
"路径和" / "最大深度" / "子树性质"DFS 后序（自底向上）需要先知道子树结果再处理当前节点
"构建树" / "序列化/反序列化"DFS 前序（自顶向下）根节点先行，方便重建结构
"BST 相关" / "第 K 小" / "有序"中序遍历BST 中序结果天然有序

通用思考框架 ​

两种递归思路 ​

解二叉树题时，先判断用哪种递归方式：

1. 分解思路（分治）

把问题拆成"左子树的答案"和"右子树的答案"，合并得到当前节点的答案。函数有返回值。

当前答案 = combine(solve(root.left), solve(root.right))

适用条件：当前节点的答案只依赖子树返回的结果，不需要路径上的全局状态。

2. 遍历思路（回溯）

用一个外部变量记录答案，遍历整棵树的过程中不断更新它。函数通常无返回值（或返回 void）。

void traverse(node) {
    // 更新全局答案
    traverse(node.left);
    traverse(node.right);
}

适用条件：需要追踪从根到当前节点的路径、或跨子树的累计状态。

选择口诀：答案只看子树结果 → 分解；需要追踪路径/全局状态 → 遍历。

四种遍历的选择 ​

遍历方式访问顺序适用场景典型题
前序根 → 左 → 右需要先处理根再处理子树序列化、构建树
中序左 → 根 → 右BST 题（结果有序）验证 BST、第 K 小
后序左 → 右 → 根需要先知道子树信息再处理根最大深度、路径和、平衡判断
层序逐层从左到右按层处理、最短距离层序遍历、右视图

基本概念 ​

节点定义（Java） ​

java
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

常见类型 ​

类型定义特点
满二叉树 Full Binary Tree每个非叶节点都有两个子节点节点数为 ， 为高度
完全二叉树 Complete Binary Tree除最后一层外，其他层节点数达到最大，且最后一层节点靠左排列堆结构的基础
二叉搜索树 BST左子树所有节点 < 根节点 < 右子树所有节点平均查找效率
AVL 树自平衡 BST，任意节点左右子树高度差 ≤ 1保证 的最坏情况

遍历模板 ​

前序遍历（根 → 左 → 右） ​

java
// 递归
List<Integer> result = new ArrayList<>();

void preorder(TreeNode root) {
    if (root == null) return;
    result.add(root.val);   // 先访问根
    preorder(root.left);
    preorder(root.right);
}

// 迭代（栈）
List<Integer> preorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;

    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);
        // 先压右再压左，保证左先出栈
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    return result;
}

中序遍历（左 → 根 → 右） ​

java
// 递归
void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    result.add(root.val);   // 中间访问根
    inorder(root.right);
}

// 迭代（栈 + curr 指针）
List<Integer> inorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root;

    while (curr != null || !stack.isEmpty()) {
        // 一路向左压栈
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        result.add(curr.val);
        curr = curr.right;  // 转向右子树
    }
    return result;
}

INFO

BST 中序遍历的结果是升序序列，这是验证/利用 BST 有序性的核心手段。

后序遍历（左 → 右 → 根） ​

java
// 递归
void postorder(TreeNode root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    result.add(root.val);   // 最后访问根
}

// 迭代（改造前序：根→右→左，然后反转结果）
List<Integer> postorderIterative(TreeNode root) {
    LinkedList<Integer> result = new LinkedList<>();
    if (root == null) return result;

    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.addFirst(node.val);  // 头插，相当于反转
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    return result;
}

层序遍历（BFS） ​

java
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 levelSize = queue.size();   // 当前层节点数
        List<Integer> level = new ArrayList<>();

        for (int i = 0; i < levelSize; 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;
}

INFO

层序遍历使用**队列（Queue）**而非栈。用 levelSize = queue.size() 在每层开始时"锁定"当前层的节点数，是控制逐层处理的标准技巧。

典型例题：二叉树的最大深度 ​

LeetCode 104 - 二叉树的最大深度

题目：给定一棵二叉树，返回其最大深度（根节点到最远叶节点的最长路径上的节点数）。

分解思路（推荐） ​

树的深度 = 1 + max(左子树深度, 右子树深度)，空树深度为 0。这是典型的后序分解。

java
public int maxDepth(TreeNode root) {
    // base case：空节点深度为 0
    if (root == null) return 0;

    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);

    // 当前节点的深度 = 子树最大深度 + 1
    return 1 + Math.max(leftDepth, rightDepth);
}
// 时间复杂度：O(n)，每个节点访问一次
// 空间复杂度：O(h)，h 为树高，递归栈深度

遍历思路（BFS 计层数） ​

也可以用层序遍历：每处理完一层深度 +1，最终层数即为最大深度。

java
public int maxDepthBFS(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int depth = 0;

    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        depth++;
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    return depth;
}

延伸题目 ​

题目链接与典型题的区别关键技巧
层序遍历LC 102BFS 模板直接应用Queue + levelSize 控制每层
翻转二叉树LC 226前序遍历，每个节点交换左右子递归先 swap 再递归两侧
对称二叉树LC 101双指针递归，同时从两侧比较比较左.left vs 右.right，左.right vs 右.left
验证 BSTLC 98需要传递整棵子树的 min/max 范围递归传边界 (min, max)，不能只比父子
从前序与中序构造二叉树LC 105前序确定根，中序划分左右子树HashMap 存中序位置，避免每次线性查找
二叉树的右视图LC 199BFS 取每层最后一个节点层序遍历变体，i == levelSize - 1 时记录
平衡二叉树LC 110后序遍历 + 提前剪枝返回 -1 表示已不平衡，避免重复计算高度

常见陷阱与调试 ​

错误症状解决方法
忘记空节点检查NullPointerException / 栈溢出递归函数第一行加 if (root == null) return ...
混淆遍历顺序结果顺序错误，BST 题值不有序记住"根"的位置：前序=根在前，中序=根居中，后序=根在后
层序用了栈而非队列遍历结果是深度优先而非按层层序必须用 Queue（FIFO），不能用 Stack（LIFO）
BST 验证只比父子关系某些非法 BST 被误判为合法递归时传递 (long min, long max) 范围边界，不能只看相邻两层
分解思路用了全局变量变量在多次调用间互相污染分解思路应通过返回值传递信息，全局变量留给遍历思路