Appearance
二叉树
二叉树是算法面试的重中之重，几乎每场面试都会涉及。本模块涵盖二叉树的遍历、深度、翻转、对称、公共祖先、路径和等核心题型。掌握递归与迭代两种遍历方式，理解前序、中序、后序和层序遍历的应用场景，是解决二叉树问题的基础。
Q1: 二叉树的最大深度 「🟢 初级」
题目描述：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
考察点：递归、树的深度定义、DFS与BFS。
解题思路：
- 方法1：递归DFS，左子树深度和右子树深度的最大值 + 1（时间O(n)，空间O(h)，h为树高）- 最优解
- 方法2：迭代BFS，层序遍历统计层数（时间O(n)，空间O(n)）
代码实现：
java
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;
}复杂度分析：时间复杂度 O(n)，每个节点访问一次；空间复杂度 O(h)，递归栈深度为树高，最坏O(n)。
变体扩展：
- 变体1：二叉树的最小深度
- 变体2：平衡二叉树
- 变体3：N叉树的最大深度
- 变体4：二叉树的直径
Q2: 二叉树的层序遍历 「🟡 中级」
题目描述：给你二叉树的根节点 root，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。
考察点：BFS广度优先搜索、队列的应用、层级记录。
解题思路：
- 方法1：BFS迭代，使用队列，每层开始时记录队列大小（时间O(n)，空间O(n)）- 最优解
- 方法2：DFS递归，用level参数标记当前层级
代码实现：
java
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
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);
}
res.add(level);
}
return res;
}复杂度分析：时间复杂度 O(n)，每个节点入队出队各一次；空间复杂度 O(n)，队列最多存储最后一层所有节点。
变体扩展：
- 变体1：二叉树的锯齿形层序遍历
- 变体2：二叉树的层序遍历II（自底向上）
- 变体3：N叉树的层序遍历
- 变体4：二叉树的右视图
Q3: 翻转二叉树 「🟢 初级」
题目描述：给你一棵二叉树的根节点 root，翻转这棵二叉树，并返回其根节点。
考察点：递归、树的遍历、交换节点。
解题思路：
- 方法1：递归DFS，前序遍历位置交换左右子节点（时间O(n)，空间O(h)）- 最优解
- 方法2：迭代BFS，层序遍历交换每个节点的左右子节点（时间O(n)，空间O(n)）
代码实现：
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;
}复杂度分析：时间复杂度 O(n)，每个节点访问一次；空间复杂度 O(h)，递归栈深度。
变体扩展：
- 变体1：对称二叉树
- 变体2：相同的树
- 变体3：另一个树的子树
Q4: 对称二叉树 「🟢 初级」
题目描述：给你一个二叉树的根节点 root，检查它是否轴对称。
考察点：递归、双指针、树的对称性判断。
解题思路：
- 方法1：递归，判断两个子树是否镜像对称（时间O(n)，空间O(h)）- 最优解
- 方法2：迭代，使用队列成对检查（时间O(n)，空间O(n)）
代码实现：
java
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return isMirror(root.left, root.right);
}
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)，递归栈深度。
变体扩展：
- 变体1：相同的树
- 变体2：翻转二叉树
- 变体3：对称树的迭代实现
Q5: 二叉树的前中后序遍历（递归+迭代） 「🟢 初级」
题目描述：给定一个二叉树的根节点 root，分别返回它的前序、中序、后序遍历。要求分别用递归和迭代两种方式实现。
考察点：二叉树遍历的本质、栈的应用、Morris遍历。
解题思路：
- 方法1：递归，最简单直观（时间O(n)，空间O(h)）
- 方法2：迭代，使用栈模拟递归（时间O(n)，空间O(h)）- 需重点掌握
- 方法3：Morris遍历，空间O(1)
代码实现：
java
// 前序遍历 - 迭代
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
res.add(node.val);
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
return res;
}
// 中序遍历 - 迭代
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = 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();
res.add(curr.val);
curr = curr.right;
}
return res;
}
// 后序遍历 - 迭代（前序翻转法）
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> res = new LinkedList<>();
if (root == null) return res;
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
res.addFirst(node.val); // 头插
if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right);
}
return res;
}复杂度分析：时间复杂度 O(n)，每个节点入栈出栈一次；空间复杂度 O(h)，栈深度为树高。
变体扩展：
- 变体1：二叉树的层序遍历
- 变体2：从前序与中序遍历序列构造二叉树
- 变体3：从中序与后序遍历序列构造二叉树
- 变体4：Morris遍历
Q6: 二叉树的最近公共祖先 「🟡 中级」
题目描述：给定一个二叉树，找到该树中两个指定节点的最近公共祖先。最近公共祖先的定义为：对于有根树T的两个节点p、q，最近公共祖先表示为一个节点x，满足x是p、q的祖先且x的深度尽可能大。
考察点：递归、后序遍历、祖先定义。
解题思路：
- 方法1：递归后序遍历，返回p或q或公共祖先（时间O(n)，空间O(h)）- 最优解
- 方法2：存储父节点路径，找第一个公共节点（时间O(n)，空间O(n)）
代码实现：
java
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; // 左右各一个，当前是LCA
return left != null ? left : right; // 都在一边，向上返回
}复杂度分析：时间复杂度 O(n)，最坏遍历所有节点；空间复杂度 O(h)，递归栈深度。
变体扩展：
- 变体1：二叉搜索树的最近公共祖先
- 变体2：N叉树的最近公共祖先
- 变体3：二叉树的所有公共祖先路径
- 变体4：最小公共祖先II（有父指针）
Q7: 路径总和 「🟢 初级」
题目描述：给你二叉树的根节点 root 和一个表示目标和的整数 targetSum。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum。
考察点：DFS递归、路径定义、回溯思想。
解题思路：
- 方法1：递归DFS，从根到叶逐步减去节点值（时间O(n)，空间O(h)）- 最优解
- 方法2：BFS迭代，使用两个队列分别存节点和当前和（时间O(n)，空间O(n)）
代码实现：
java
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);
}复杂度分析：时间复杂度 O(n)，最坏遍历所有节点；空间复杂度 O(h)，递归栈深度。
变体扩展：
- 变体1：路径总和II（返回所有路径）
- 变体2：路径总和III（任意起点终点）
- 变体3：求根到叶子节点数字之和
- 变体4：二叉树的所有路径
Q8: 路径总和III 「🟡 中级」
题目描述：给定一个二叉树的根节点 root，和一个整数 targetSum，求该二叉树里节点值之和等于 targetSum 的路径的数目。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
考察点：双重递归、前缀和、路径计数。
解题思路：
- 方法1：双重递归，外层遍历每个节点作为起点，内层DFS统计路径数（时间O(n²)，空间O(h)）
- 方法2：前缀和 + 回溯，类似两数之和思路（时间O(n)，空间O(h)）- 最优解
代码实现：
java
// 方法1：双重递归
public int pathSum(TreeNode root, int targetSum) {
if (root == null) return 0;
return pathSumFrom(root, targetSum)
+ pathSum(root.left, targetSum)
+ pathSum(root.right, targetSum);
}
private int pathSumFrom(TreeNode node, long sum) {
if (node == null) return 0;
sum -= node.val;
return (sum == 0 ? 1 : 0)
+ pathSumFrom(node.left, sum)
+ pathSumFrom(node.right, sum);
}复杂度分析：双重递归时间复杂度 O(n²)，每个节点作为起点都要遍历子树；空间复杂度 O(h)。
变体扩展：
- 变体1：路径总和
- 变体2：路径总和II
- 变体3：路径总和IV
- 变体4：二叉树中的最大路径和
Q9: 验证二叉搜索树 「🟡 中级」
题目描述：给你一个二叉树的根节点 root，判断其是否是一个有效的二叉搜索树。有效二叉搜索树定义如下：节点的左子树只包含小于当前节点的数，节点的右子树只包含大于当前节点的数，所有左子树和右子树自身必须也是二叉搜索树。
考察点：二叉搜索树性质、中序遍历递增、上下界递归。
解题思路：
- 方法1：递归，传入上下界约束（时间O(n)，空间O(h)）- 最优解
- 方法2：中序遍历，判断是否严格递增（时间O(n)，空间O(h)）
代码实现：
java
// 递归 - 上下界
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean isValidBST(TreeNode node, long lower, long upper) {
if (node == null) return true;
if (node.val <= lower || node.val >= upper) return false;
return isValidBST(node.left, lower, node.val)
&& isValidBST(node.right, node.val, upper);
}复杂度分析：时间复杂度 O(n)，每个节点访问一次；空间复杂度 O(h)，递归栈深度。
变体扩展：
- 变体1：二叉搜索树的中序遍历
- 变体2：恢复二叉搜索树
- 变体3：将有序数组转换为二叉搜索树
- 变体4：二叉搜索树的第k小元素
Q10: 二叉树中的最大路径和 「🔴 高级」
题目描述：二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中至多出现一次。该路径至少有一个节点，且不一定经过根节点。路径和是路径中各节点值的总和。给你一个二叉树的根节点 root，返回其最大路径和。
考察点：后序遍历、动态规划思想、最大贡献值。
解题思路：
- 方法：后序遍历递归，计算每个节点的最大贡献值（只能选左右一边），同时更新全局最大路径和（可以左右都选加上当前节点）（时间O(n)，空间O(h)）- 最优解
代码实现：
java
class Solution {
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(maxGain(node.left), 0);
int rightGain = Math.max(maxGain(node.right), 0);
// 以当前节点为最高点的路径和
int priceNewPath = node.val + leftGain + rightGain;
maxSum = Math.max(maxSum, priceNewPath);
// 返回给父节点的最大贡献（只能选一边）
return node.val + Math.max(leftGain, rightGain);
}
}复杂度分析：时间复杂度 O(n)，每个节点访问一次；空间复杂度 O(h)，递归栈深度，最坏O(n)。
变体扩展：
- 变体1：二叉树的直径
- 变体2：路径总和III
- 变体3：最长同值路径
- 变体4：二叉树的最大深度