算法面试突击手册 —— 二叉树（DFS/BFS）
一、概念与特点
大白话 + 类比
二叉树 = 家族谱系图
每个节点有两个分支（左孩子、右孩子），就像一个人的两个孩子。递归是最自然的思维方式——你想统计整个家族的人数，不需要自己一个一个数，而是问左孩子”你家多少人”，再问右孩子”你家多少人”，加自己就是答案。这就是后序遍历的直觉。
核心遍历方式
| 遍历 | 顺序 | 类比 | 典型应用 |
|---|---|---|---|
| 前序 | 根→左→右 | 先自己，再孩子 | 序列化、构造树 |
| 中序 | 左→根→右 | BST = 有序输出 | 验证 BST、第 K 小 |
| 后序 | 左→右→根 | 先孩子，后自己 | 求深度/直径、最大路径和 |
| 层序（BFS） | 一层一层 | 排队入场 | 右视图、最大宽度 |
核心特征（什么时候该想到用树）
| 特征 | 说明 |
|---|---|
| 递归结构 | 树天然递归，左子树+右子树+根 |
| 遍历/搜索 | DFS（前中后序）、BFS（层序） |
| 子树/路径 | 自底向上聚合信息（后序） |
| BST 性质 | 左 < 根 < 右，中序有序 |
识别信号词
- “二叉树”、“结点” → 直接是树题
- “深度”、“高度”、“直径” → 后序遍历
- “层序”、“按层”、“右视图” → BFS（队列）
- “二叉搜索树”、“BST” → 中序遍历 + BST 性质
- “路径”、“路径和” → DFS 后序遍历
二、应用场景
两种遍历模板
// DFS（递归后序）
int dfs(TreeNode root) {
if (root == null) return 0;
int left = dfs(root.left);
int right = dfs(root.right);
return 1 + Math.max(left, right); // 例：求高度
}
// BFS（层序）
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
// 处理当前节点
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}三、Hot 100 精讲题目
104. Maximum Depth of Binary Tree 二叉树的最大深度
📌 求二叉树的最大深度（根到最远叶子的节点数）。如
[3,9,20,null,null,15,7]→ 3
🔍 解题分析
核心思路（后序）：树的最大深度 = 1 + max(左子树深度, 右子树深度)。空树深度为 0。
✅ 完整 Java 实现
public int maxDepth(TreeNode root) {
if (root == null) return 0;
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return 1 + Math.max(leftDepth, rightDepth);
}💡 记忆口诀
“空树为 0，非空 = 1 + 左右深的较大者”
94. Binary Tree Inorder Traversal 二叉树的中序遍历
📌 返回二叉树的中序遍历结果。
✅ 完整 Java 实现
// 递归
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorder(root, result);
return result;
}
private void inorder(TreeNode node, List<Integer> result) {
if (node == null) return;
inorder(node.left, result);
result.add(node.val);
inorder(node.right, result);
}
// 迭代（栈模拟）
public List<Integer> inorderTraversal_iter(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
// 一路向左走到底
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop(); // 左到底了，弹出根
result.add(cur.val); // 访问根
cur = cur.right; // 转向右子树
}
return result;
}💡 记忆口诀
“一路向左走到底，弹出来访问后转到右边”
226. Invert Binary Tree 翻转二叉树
📌 翻转二叉树，镜像每一层的左右子树。
🔍 解题分析
核心思路（前序/后序都可以）：交换当前节点的左右孩子，然后递归翻转左右子树。
✅ 完整 Java 实现
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
// 交换左右孩子
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
// 递归翻转子树
invertTree(root.left);
invertTree(root.right);
return root;
}💡 记忆口诀
“左右互换，递归到底”
101. Symmetric Tree 对称二叉树
📌 判断二叉树是否镜像对称。
🔍 解题分析
核心思路：双指针同时递归。p 走左子树时 q 走右子树，递归比较 p.left vs q.right 以及 p.right vs q.left。
✅ 完整 Java 实现
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null) return false;
// 值相等 + p 的左 vs q 的右 + p 的右 vs q 的左
return p.val == q.val
&& isMirror(p.left, q.right)
&& isMirror(p.right, q.left);
}💡 记忆口诀
“两个指针镜像走，值相等且交叉递归”
543. Diameter of Binary Tree 二叉树的直径
📌 直径定义为任意两节点间的最长路径长度（边数）。可能不经过根。
🔍 解题分析
核心思路（后序）：对每个节点，经过它的最长路径 = 左子树深度 + 右子树深度。全局最大直径就是所有节点的这个值中的最大值。
关键：深度和直径是两个概念。返回深度给父节点，用深度算直径并更新全局答案。这是后序遍历的经典模式：返回一个值，更新另一个值。
✅ 完整 Java 实现
private int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxDepth(root);
return maxDiameter;
}
// 返回以 node 为根的子树深度，同时更新全局直径
private int maxDepth(TreeNode node) {
if (node == null) return 0;
int left = maxDepth(node.left);
int right = maxDepth(node.right);
// 经过当前节点的直径 = 左深 + 右深
maxDiameter = Math.max(maxDiameter, left + right);
// 返回深度给父节点
return 1 + Math.max(left, right);
}💡 记忆口诀
“后序求深度，左右深度和更新直径”
102. Binary Tree Level Order Traversal 二叉树的层序遍历
📌 按层返回节点的值列表。如
[3,9,20,null,null,15,7]→[[3],[9,20],[15,7]]
🔍 解题分析
核心思路（BFS + 队列）：用队列存储当前层的节点。每轮处理队列中全部节点（即当前层的所有节点），同时把下一层节点入队。
✅ 完整 Java 实现
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 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;
}💡 记忆口诀
“队列存当前层，size 记录该层几个”
108. Convert Sorted Array to BST 有序数组转二叉搜索树
📌 将一个升序数组转换成高度平衡的 BST。
🔍 解题分析
核心思路：二分法选根。数组中间元素做根，左边子数组构造左子树，右边子数组构造右子树。递归完成。
✅ 完整 Java 实现
public TreeNode sortedArrayToBST(int[] nums) {
return buildBST(nums, 0, nums.length - 1);
}
private TreeNode buildBST(int[] nums, int left, int right) {
if (left > right) return null;
int mid = left + (right - left) / 2; // 中间位置做根
TreeNode root = new TreeNode(nums[mid]);
root.left = buildBST(nums, left, mid - 1);
root.right = buildBST(nums, mid + 1, right);
return root;
}💡 记忆口诀
“中间做根，左边造左树，右边造右树”
98. Validate Binary Search Tree 验证二叉搜索树
📌 判断一棵二叉树是否为有效的 BST。
🔍 解题分析
方法一：递归传范围
- 每个节点必须在一个合法区间内
- 左子节点区间：
(min, root.val) - 右子节点区间：
(root.val, max)
方法二：中序遍历
- BST 的中序遍历是严格递增序列
- 维护一个 pre 记录前一个访问的节点值
✅ 完整 Java 实现
// 方法一：递归传范围（推荐）
public boolean isValidBST(TreeNode root) {
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean validate(TreeNode node, long min, long max) {
if (node == null) return true;
if (node.val <= min || node.val >= max) return false;
// 左子树区间：(min, node.val)，右子树区间：(node.val, max)
return validate(node.left, min, node.val)
&& validate(node.right, node.val, max);
}
// 方法二：中序遍历
private TreeNode prev = null;
public boolean isValidBST_inorder(TreeNode root) {
if (root == null) return true;
if (!isValidBST_inorder(root.left)) return false;
if (prev != null && prev.val >= root.val) return false;
prev = root;
return isValidBST_inorder(root.right);
}💡 记忆口诀
“每个节点在区间内，左紧右紧递归传”
230. Kth Smallest Element in a BST 二叉搜索树中第 K 小的元素
📌 找到 BST 中第 K 小的元素。
🔍 解题分析
核心思路：BST 中序遍历即升序。中序遍历到第 K 个节点时返回。
✅ 完整 Java 实现
private int count = 0;
private int answer = 0;
public int kthSmallest(TreeNode root, int k) {
count = k;
inorder(root);
return answer;
}
private void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
count--;
if (count == 0) {
answer = node.val;
return;
}
inorder(node.right);
}💡 记忆口诀
“中序遍历走起，数到第 K 个就停下”
199. Binary Tree Right Side View 二叉树的右视图
📌 返回从右侧看到的节点值（每层最右边的节点）。
🔍 解题分析
核心思路（BFS）：层序遍历，每层最后一个节点就是右视图看到的节点。
✅ 完整 Java 实现
public List<Integer> rightSideView(TreeNode root) {
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();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (i == size - 1) result.add(node.val); // 每层最后一个
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
return result;
}💡 记忆口诀
“层序遍历，每层收最后一个”
114. Flatten Binary Tree to Linked List 二叉树展开为链表
📌 将二叉树原地展开为单链表（右指针做 next），顺序与前序遍历相同。
🔍 解题分析
核心思路（后序）：从下往上摊平。先把左右子树都展平，然后：左链表接到 root.right，右链表接到左链表末端。
✅ 完整 Java 实现
public void flatten(TreeNode root) {
if (root == null) return;
// 后序：先展平左右
flatten(root.left);
flatten(root.right);
// 暂存左右
TreeNode left = root.left;
TreeNode right = root.right;
// 左子树移到右边
root.left = null;
root.right = left;
// 找到当前右链的末端，把原来的右子树接上去
TreeNode cur = root;
while (cur.right != null) {
cur = cur.right;
}
cur.right = right;
}💡 记忆口诀
“后序展平左右，左挂右，右挂左链尾”
105. Construct Binary Tree from Preorder and Inorder 从前序与中序构造二叉树
📌 给定前序和中序遍历结果，构造二叉树。
🔍 解题分析
核心思路：前序第一个是根。在中序中找到根的位置，左边是左子树，右边是右子树。递归构造。
✅ 完整 Java 实现
// 用 HashMap 记录中序遍历中 值→下标，快速定位根的位置
private Map<Integer, Integer> inorderMap = new HashMap<>();
private int preIdx = 0; // 当前前序中的位置
public TreeNode buildTree(int[] preorder, int[] inorder) {
for (int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
return build(preorder, 0, inorder.length - 1);
}
private TreeNode build(int[] preorder, int inLeft, int inRight) {
if (inLeft > inRight) return null;
int rootVal = preorder[preIdx++]; // 前序第一个是根
TreeNode root = new TreeNode(rootVal);
int rootInIdx = inorderMap.get(rootVal); // 根在中序的位置
root.left = build(preorder, inLeft, rootInIdx - 1); // 左子树
root.right = build(preorder, rootInIdx + 1, inRight); // 右子树
return root;
}💡 记忆口诀
“前序第一个是根，中序找根分左右”
236. Lowest Common Ancestor 二叉树的最近公共祖先
📌 找两个指定节点的最近公共祖先。
🔍 解题分析
核心思路（后序）：自底向上查找。如果当前节点是 p 或 q 之一，返回当前节点。否则看左右子树：如果左右各返回了一个非 null（说明 p 和 q 分别在左右），当前节点就是 LCA；如果只有一边非 null，返回那一边。
✅ 完整 Java 实现
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root; // 找到了 p 或 q，或者到底了
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 左右各有一个 → 当前节点就是 LCA
if (left != null && right != null) return root;
// 只有一边有 → 返回那边往上传递
return left != null ? left : right;
}💡 记忆口诀
“左右各找到一个，我就是祖先；只有一边有，往上传递”
124. Binary Tree Maximum Path Sum 二叉树中的最大路径和
📌 求任意一条节点序列（至少一个节点）的最大路径和。路径可以不经过根。
🔍 解题分析
核心思路（后序，类似 543 直径）：对每个节点，计算经过它的最大路径和 = root.val + max(0, 左子树贡献) + max(0, 右子树贡献)。返回给父节点的是 root.val + max(0, max(左贡献, 右贡献))。
关键：负数不取（用 max(0, …)）。贡献和路径和是两个值，返回一个，更新另一个。
✅ 完整 Java 实现
private int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxGain(root);
return maxSum;
}
// 返回以 node 为起点向下延伸的最大单边贡献
private int maxGain(TreeNode node) {
if (node == null) return 0;
// 左右子树贡献，负的就不要
int leftGain = Math.max(0, maxGain(node.left));
int rightGain = Math.max(0, maxGain(node.right));
// 经过当前节点的最大路径和
int pathSum = node.val + leftGain + rightGain;
maxSum = Math.max(maxSum, pathSum);
// 返回单边最大贡献给父节点
return node.val + Math.max(leftGain, rightGain);
}💡 记忆口诀
“左右贡献取正，全路径和更新最大，单边返回给父”
538. Convert BST to Greater Tree 把二叉搜索树转换为累加树
📌 使每个节点的值变成原树中大于等于它的节点值之和。
🔍 解题分析
核心思路（反向中序：右→根→左）：反向中序遍历，维护一个累加和 sum。访问每个节点时 sum += node.val，然后把 node.val 设成 sum。
✅ 完整 Java 实现
private int sum = 0;
public TreeNode convertBST(TreeNode root) {
reverseInorder(root);
return root;
}
private void reverseInorder(TreeNode node) {
if (node == null) return;
reverseInorder(node.right); // 先右边（更大值）
sum += node.val; // 累加
node.val = sum; // 更新节点值
reverseInorder(node.left); // 再左边（更小值）
}💡 记忆口诀
“反着中序：右→根→左，一路累加”
617. Merge Two Binary Trees 合并二叉树
📌 合并两棵树，对应节点值相加。某节点为 null 时取另一棵树的节点。
🔍 解题分析
核心思路（同步递归）：两棵树一起遍历。如果一边为 null 返回另一边；否则值相加，左右孩子递归合并。
✅ 完整 Java 实现
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) return root2;
if (root2 == null) return root1;
root1.val += root2.val;
root1.left = mergeTrees(root1.left, root2.left);
root1.right = mergeTrees(root1.right, root2.right);
return root1;
}💡 记忆口诀
“有一边 null 取另一边，都不空就相加合并”
297. Serialize and Deserialize Binary Tree 二叉树的序列化与反序列化
📌 把二叉树编码为字符串并能解码还原。
🔍 解题分析
核心思路（前序遍历）：前序序列化，null 用 “N” 标记，节点间用逗号分隔。反序列化时用队列/列表按前序重建。
✅ 完整 Java 实现
public String serialize(TreeNode root) {
if (root == null) return "N";
// 前序：根,左,右
return root.val + "," + serialize(root.left) + "," + serialize(root.right);
}
public TreeNode deserialize(String data) {
Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(",")));
return buildTree(queue);
}
private TreeNode buildTree(Queue<String> queue) {
String val = queue.poll();
if (val.equals("N")) return null;
TreeNode node = new TreeNode(Integer.parseInt(val));
node.left = buildTree(queue);
node.right = buildTree(queue);
return node;
}💡 记忆口诀
“前序序列化 null 标 N，反序列化遇 N 返回 null”