二叉树算法

一、二叉树总纲（和 DFS 的关系）

二叉树题 本质 90% 都是 DFS，区别只在于：

• 访问时机不同（前 / 中 / 后序）
• 是否需要返回值（自底向上 or 自顶向下）

一句话：

树 = 无环图，DFS 天然适配

---

二、三大遍历（必须条件反射）

2.1 定义（先背死）

遍历	顺序	典型用途
前序	根 → 左 → 右	构建 / 拷贝树、路径问题
中序	左 → 根 → 右	BST（有序性）
后序	左 → 右 → 根	子树信息汇总（高度、直径、是否平衡）

2.2 模板（Java）

void preorder(TreeNode root) {
    if (root == null) return;
    visit(root);
    preorder(root.left);
    preorder(root.right);
}

void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    visit(root);
    inorder(root.right);
}

void postorder(TreeNode root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    visit(root);
}

---

三、二叉树四大题型（99% 归类）

① 路径类（自顶向下 DFS）

特征关键词：

• 根到叶
• 路径和
• 所有路径

核心思想：

路径是“过程数据”，必须 DFS + 回溯

通用模板

void dfs(TreeNode node, List<Integer> path) {
    if (node == null) return;

    path.add(node.val);          // 选择

    if (node.left == null && node.right == null) {
        // 叶子节点，记录答案
    }

    dfs(node.left, path);
    dfs(node.right, path);

    path.remove(path.size() - 1); // 回溯
}

必刷题：

• LC 112 路径总和
• LC 113 路径总和 II
• LC 257 二叉树的所有路径

---

② 子树信息类（自底向上 DFS / 后序）

特征关键词：

• 高度 / 深度
• 是否平衡
• 直径 / 最大路径

核心思想：

当前节点依赖左右子树结果 → 后序遍历

通用模板

int dfs(TreeNode root) {
    if (root == null) return 0;

    int left = dfs(root.left);
    int right = dfs(root.right);

    // 在这里“汇总左右子树信息”

    return Math.max(left, right) + 1;
}

后序: 访问当前节点时，只需要记录的右边节点有没有被访问，即上次出栈的节点是不是右侧节点；

// 左右中 + stack
const postorderTraversal = (root) => {
  if (!root) return []

  const stack = [];
  const res = [];

  let node = root;
  let prev = null

  while (stack.length || node) {
    while (node) {
      stack.push(node);

      node = node.left;
    }

    node = stack.at(-1);

    // 【1，2，3】输出：【2，3，1】
    // 执行过程中左右按顺序压入栈。左边节点到达顶点，
    // 将左侧节点值放入result, node置为空，防止走入 node left的循环；
    // 左侧节点出栈；
    // 访问右侧节点；右侧节点入栈；
    // 到达右侧顶点；右侧值放入result,
    // 节点出栈，记录右侧出栈节点，防止再次进入右侧节点；

    if (!node.right || node.right === prev) {
      res.push(node.val);
      stack.pop();

      prev = node;

      node = null;
    } else {
      node = node.right
    }
  }

  return res;
}

必刷题：

• LC 104 二叉树的最大深度
• LC 110 平衡二叉树
• LC 543 二叉树的直径

---

③ BST 类（中序有序）

特征关键词：

• 二叉搜索树
• 第 k 小 / 验证 BST

核心思想：

BST 的 中序遍历 = 升序数组

模板（中序）

void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    // root.val 在这里是“当前最小未访问值”
    inorder(root.right);
}

必刷题：

• LC 98 验证二叉搜索树
• LC 230 二叉搜索树中第 K 小的元素

---

④ 层序 / BFS 类

特征关键词：

• 一层一层
• 最短距离
• 每层统计

BFS 模板

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

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

必刷题：

• LC 102 二叉树的层序遍历
• LC 111 二叉树的最小深度
• LC 199 二叉树的右视图

---

四、10 秒判断用 DFS 还是 BFS

题目特征	算法
根到叶路径 / 所有方案	DFS + 回溯
子树高度 / 平衡 / 直径	DFS（后序）
层级 / 最短路径	BFS
BST 有序性	中序 DFS

---

五、二叉树必刷 10 题清单

1. LC 104 二叉树的最大深度
2. LC 111 二叉树的最小深度
3. LC 112 路径总和
4. LC 113 路径总和 II
5. LC 257 二叉树的所有路径
6. LC 110 平衡二叉树
7. LC 543 二叉树的直径
8. LC 102 层序遍历
9. LC 98 验证 BST
10. LC 230 BST 第 K 小