二叉树问题概述
二叉树是算法面试的绝对核心模块，它天然契合递归思维，几乎每道题都可以用递归或迭代实现。二叉树的解题技巧可归纳为三类：
- 遍历框架：前序、中序、后序（DFS）和层序（BFS），是所有题目的基础。
- 递归分解：将问题拆分为左子树、右子树和根节点的处理，如最大深度、翻转、对称、路径和等。
- 回溯与路径：利用 DFS 遍历所有根到叶子的路径，处理路径和、最近公共祖先等。
LeetCode 热门 100 题中共有 15 道二叉树题，覆盖了上述所有场景。下面按技巧分类展开。
一、基础遍历与性质（94、104、226、101）
94. 二叉树的中序遍历
题目：返回二叉树的中序遍历（左-根-右）。
核心思路：递归或迭代（栈）。递归最简洁，迭代则模拟栈过程。
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inorder(root, res);
return res;
}
private void inorder(TreeNode node, List<Integer> res) {
if (node == null) return;
inorder(node.left, res);
res.add(node.val);
inorder(node.right, res);
}
复杂度：时间 O(n)，空间 O(h)（递归栈）。
104. 二叉树的最大深度
题目：返回二叉树的最大深度（根节点到最远叶子节点数）。
核心思路：递归，maxDepth(root) = 1 + max(maxDepth(left), maxDepth(right))。
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
复杂度：时间 O(n)，空间 O(h)。
226. 翻转二叉树
题目：将二叉树左右子树交换。
核心思路：递归，先翻转左右子树，再交换当前节点的左右指针。
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
复杂度：时间 O(n)，空间 O(h)。
101. 对称二叉树
题目：判断二叉树是否镜像对称。
核心思路：递归比较左右子树是否互为镜像。定义辅助函数 isMirror(t1, t2)，检查 t1.val == t2.val 且 isMirror(t1.left, t2.right) 且 isMirror(t1.right, t2.left)。
public boolean isSymmetric(TreeNode root) {
return isMirror(root, root);
}
private boolean isMirror(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
return t1.val == t2.val && isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
}
复杂度：时间 O(n)，空间 O(h)。
二、层序与构造（102、108）
102. 二叉树的层序遍历
题目：按层返回节点值（每层一个列表）。
核心思路：BFS 使用队列，记录每层的节点数，逐层收集。
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
level.add(node.val);
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
res.add(level);
}
return res;
}
复杂度：时间 O(n)，空间 O(n)。
108. 将有序数组转换为二叉搜索树
题目：将升序数组转换为高度平衡的二叉搜索树（BST）。
核心思路：每次取中间元素作为根，递归构造左右子树。
public TreeNode sortedArrayToBST(int[] nums) {
return build(nums, 0, nums.length - 1);
}
private TreeNode build(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 = build(nums, left, mid - 1);
root.right = build(nums, mid + 1, right);
return root;
}
复杂度：时间 O(n)，空间 O(log n)（递归栈）。
三、BST 性质（98、230）
98. 验证二叉搜索树
题目：判断二叉树是否满足 BST 性质（左 < 根 < 右）。
核心思路：中序遍历应为升序，或递归传递上下界。
public boolean isValidBST(TreeNode root) {
return validate(root, null, null);
}
private boolean validate(TreeNode node, Integer low, Integer high) {
if (node == null) return true;
if ((low != null && node.val <= low) || (high != null && node.val >= high)) return false;
return validate(node.left, low, node.val) && validate(node.right, node.val, high);
}
复杂度：时间 O(n)，空间 O(h)。
230. 二叉搜索树中第 K 小的元素
题目：返回 BST 中第 k 小的元素（k 从 1 开始）。
核心思路：中序遍历，计数到 k 时返回。
public int kthSmallest(TreeNode root, int k) {
int[] count = new int[]{k};
int[] res = new int[1];
inorder(root, count, res);
return res[0];
}
private void inorder(TreeNode node, int[] count, int[] res) {
if (node == null) return;
inorder(node.left, count, res);
count[0]--;
if (count[0] == 0) {
res[0] = node.val;
return;
}
inorder(node.right, count, res);
}
复杂度：时间 O(n)（最坏），空间 O(h)。
四、路径与构造（199、114、105、437）
199. 二叉树的右视图
题目：返回从右边看二叉树能看到的节点值（每层最右）。
核心思路：BFS 层序，记录每层最后一个节点；或 DFS 先右后左，当深度等于已收集数量时加入。
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
dfs(root, 0, res);
return res;
}
private void dfs(TreeNode node, int depth, List<Integer> res) {
if (node == null) return;
if (depth == res.size()) res.add(node.val);
dfs(node.right, depth + 1, res);
dfs(node.left, depth + 1, res);
}
复杂度：时间 O(n)，空间 O(h)。
114. 二叉树展开为链表
题目：将二叉树按前序遍历顺序展开为单向链表（右指针指向下一个）。
核心思路：后序递归，将左子树展平并接入右子树位置，然后将原右子树接在左子树末尾。
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;
}
复杂度：时间 O(n)，空间 O(h)。
105. 从前序与中序遍历序列构造二叉树
题目：根据前序和中序数组构造二叉树（无重复值）。
核心思路：前序第一个为根，在中序中找到根的位置，递归构造左右子树。用哈希表优化定位。
public TreeNode buildTree(int[] preorder, int[] inorder) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) map.put(inorder[i], i);
return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, map);
}
private TreeNode build(int[] preorder, int pLeft, int pRight,
int[] inorder, int iLeft, int iRight,
Map<Integer, Integer> map) {
if (pLeft > pRight) return null;
int rootVal = preorder[pLeft];
TreeNode root = new TreeNode(rootVal);
int idx = map.get(rootVal);
int leftSize = idx - iLeft;
root.left = build(preorder, pLeft + 1, pLeft + leftSize,
inorder, iLeft, idx - 1, map);
root.right = build(preorder, pLeft + leftSize + 1, pRight,
inorder, idx + 1, iRight, map);
return root;
}
复杂度：时间 O(n)，空间 O(n)。
437. 路径总和 III
题目：给定二叉树和目标值，求节点值之和等于目标值的路径总数（路径不必从根开始，也不用到叶）。
核心思路：前缀和 + DFS 回溯。用哈希表记录从根到当前节点的路径和出现次数，类似于"和为 K 的子数组"的树版本。
public int pathSum(TreeNode root, int targetSum) {
Map<Long, Integer> prefix = new HashMap<>();
prefix.put(0L, 1);
return dfs(root, 0L, targetSum, prefix);
}
private int dfs(TreeNode node, long currentSum, int target, Map<Long, Integer> prefix) {
if (node == null) return 0;
currentSum += node.val;
int count = prefix.getOrDefault(currentSum - target, 0);
prefix.put(currentSum, prefix.getOrDefault(currentSum, 0) + 1);
count += dfs(node.left, currentSum, target, prefix);
count += dfs(node.right, currentSum, target, prefix);
prefix.put(currentSum, prefix.get(currentSum) - 1); // 回溯
return count;
}
复杂度：时间 O(n)，空间 O(n)。
五、最近公共祖先与最大路径和（236、124）
236. 二叉树的最近公共祖先
题目：给定两个节点 p、q，返回它们的最近公共祖先（LCA）。
核心思路：递归，若当前节点为 null 或等于 p/q 则返回当前节点；在左右子树中查找，若两边均非空则当前节点为 LCA，否则返回非空的一侧。
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;
}
复杂度：时间 O(n)，空间 O(h)。
124. 二叉树中的最大路径和
题目：路径可以从任意节点到任意节点，求最大路径和（路径至少包含一个节点）。
核心思路：递归计算每个节点的"最大贡献值"（即从该节点向下延伸能获得的最大和），同时全局更新以该节点为最高点的最大路径和（左贡献 + 右贡献 + 自身值）。注意贡献值为负数时取 0（不延伸）。
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxGain(root);
return maxSum;
}
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 currentPathSum = node.val + leftGain + rightGain;
maxSum = Math.max(maxSum, currentPathSum);
return node.val + Math.max(leftGain, rightGain);
}
复杂度：时间 O(n)，空间 O(h)。
六、对比与总结
| 题目 | 核心技巧 | 时间复杂度 | 空间复杂度 | 关键点 |
|---|---|---|---|---|
| 94 中序遍历 | DFS（递归/迭代） | O(n) | O(h) | 递归或显式栈 |
| 104 最大深度 | 递归分解 | O(n) | O(h) | 1 + max(left,right) |
| 226 翻转二叉树 | 递归交换 | O(n) | O(h) | 先翻转子树再交换 |
| 101 对称二叉树 | 递归镜像比较 | O(n) | O(h) | 比较 t1.left vs t2.right |
| 102 层序遍历 | BFS（队列） | O(n) | O(n) | 每层节点数控制 |
| 108 有序数组转 BST | 分治构造 | O(n) | O(log n) | 取中间为根 |
| 98 验证 BST | 上下界递归 | O(n) | O(h) | 传递 low/high |
| 230 第 K 小元素 | 中序遍历 | O(n) | O(h) | 计数剪枝 |
| 199 右视图 | DFS 先右后左 | O(n) | O(h) | 深度匹配列表大小 |
| 114 展开为链表 | 后序递归 | O(n) | O(h) | 左接右，右接原右 |
| 105 前中构造 | 分治+哈希 | O(n) | O(n) | 定位根位置 |
| 437 路径总和 III | 前缀和+回溯 | O(n) | O(n) | 类似子数组和 |
| 236 最近公共祖先 | 递归查找 | O(n) | O(h) | 左右均非空则返回根 |
| 124 最大路径和 | 后序贡献计算 | O(n) | O(h) | 负数贡献取 0 |
总结心法：
- 二叉树题几乎都可以用递归解决，关键是明确递归函数的意义（返回值是什么，副作用是什么）。
- 对于路径类问题，常用"前缀和 + 回溯"或"全局最大值"方式。
- 构造类问题（如由遍历序列构造）依赖分治，用哈希表优化定位。
- 最近公共祖先和最大路径和是难点，但思路固定，熟记模板即可。