树与图
树和图是面试中的重要考点，主要考察二叉树的遍历、BST操作、图的搜索算法等。
面试题 04.01. 节点间通路
题目描述
节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。
示例 1：
输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
输出：true
示例 2：
输入：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]], start = 0, target = 4
输出：true
解题思路
使用 BFS 或 DFS 从起点开始搜索，看是否能到达终点。首先需要根据 graph 构建邻接表。
Java 代码实现
BFS 解法：
class Solution {
public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : graph) {
adj.get(edge[0]).add(edge[1]);
}
boolean[] visited = new boolean[n];
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
visited[start] = true;
while (!queue.isEmpty()) {
int cur = queue.poll();
if (cur == target) return true;
for (int next : adj.get(cur)) {
if (!visited[next]) {
visited[next] = true;
queue.offer(next);
}
}
}
return false;
}
}
面试题 04.02. 最小高度树
题目描述
给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。
示例：
给定有序数组: [-10,-3,0,5,9]
一个可能的答案是：[0,-3,9,-10,null,5]，可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
解题思路
要使 BST 高度最小，需要选择中间元素作为根节点，这样左右子树的节点数相差不超过 1。递归地对左右子数组进行同样的操作。
Java 代码实现
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return buildTree(nums, 0, nums.length - 1);
}
private TreeNode buildTree(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 = buildTree(nums, left, mid - 1);
root.right = buildTree(nums, mid + 1, right);
return root;
}
}
面试题 04.03. 特定深度节点链表
题目描述
给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。
示例：
输入：[1,2,3,4,5,null,7,8]
1
/ \
2 3
/ \ \
4 5 7
/
8
输出：[[1],[2,3],[4,5,7],[8]]
解题思路
使用 BFS 层序遍历二叉树，每一层的节点组成一个链表。
Java 代码实现
class Solution {
public ListNode[] listOfDepth(TreeNode tree) {
if (tree == null) return new ListNode[0];
List<ListNode> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(tree);
while (!queue.isEmpty()) {
int size = queue.size();
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
cur.next = new ListNode(node.val);
cur = cur.next;
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(dummy.next);
}
return result.toArray(new ListNode[0]);
}
}
面试题 04.04. 检查平衡性
题目描述
实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。
示例 1：
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
示例 2：
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。
解题思路
递归计算每个节点的左右子树高度，如果高度差超过 1，则不平衡。可以在计算高度的同时进行判断，如果发现不平衡直接返回 -1。
Java 代码实现
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root) != -1;
}
private int height(TreeNode node) {
if (node == null) return 0;
int leftHeight = height(node.left);
if (leftHeight == -1) return -1;
int rightHeight = height(node.right);
if (rightHeight == -1) return -1;
if (Math.abs(leftHeight - rightHeight) > 1) return -1;
return Math.max(leftHeight, rightHeight) + 1;
}
}
面试题 04.05. 合法二叉搜索树
题目描述
实现一个函数，检查一棵二叉树是否为二叉搜索树。
示例 1：
输入：
2
/ \
1 3
输出：true
示例 2：
输入：
5
/ \
1 4
/ \
3 6
输出：false
解释：输入为：[5,1,4,null,null,3,6]，根节点的值为 5 ，但是其右子节点值为 4 。
解题思路
方法一：中序遍历
BST 的中序遍历结果是递增的，可以检查遍历结果是否递增。
方法二：递归验证
每个节点的值必须在一个范围内：左子树的所有节点值小于当前节点，右子树的所有节点值大于当前节点。
Java 代码实现
递归验证：
class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}
private boolean isValidBST(TreeNode node, Integer min, Integer max) {
if (node == null) return true;
if (min != null && node.val <= min) return false;
if (max != null && node.val >= max) return false;
return isValidBST(node.left, min, node.val) &&
isValidBST(node.right, node.val, max);
}
}
中序遍历：
class Solution {
private long prev = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
if (!isValidBST(root.left)) return false;
if (root.val <= prev) return false;
prev = root.val;
return isValidBST(root.right);
}
}
面试题 04.06. 后继者
题目描述
设计一个算法，找出二叉搜索树中指定节点的"下一个"节点（也即中序后继）。如果指定节点没有对应的"下一个"节点，则返回 null。
示例 1：
输入: root = [2,1,3], p = 1
输出: 2
示例 2：
输入: root = [5,3,6,2,4,null,null,1], p = 6
输出: null
解题思路
方法一：利用 BST 性质
如果 p 有右子树，则后继是右子树的最左节点。如果 p 没有右子树，则后继是从根到 p 的路径上第一个大于 p 的节点。
方法二：中序遍历
中序遍历 BST，找到 p 后的下一个节点。
Java 代码实现
利用 BST 性质：
class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode successor = null;
while (root != null) {
if (root.val > p.val) {
successor = root;
root = root.left;
} else {
root = root.right;
}
}
return successor;
}
}
面试题 04.08. 首个共同祖先
题目描述
设计并实现一个算法，找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。注意：这不一定是二叉搜索树。
示例 1：
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
解题思路
递归查找 p 和 q。如果当前节点是 p 或 q，则返回当前节点。如果在左右子树分别找到了 p 和 q，则当前节点就是 LCA。如果只在一边找到了，则返回找到的那边。
Java 代码实现
class Solution {
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;
}
}
面试题 04.09. 二叉搜索树序列
题目描述
从左向右遍历一个数组，通过不断将其中的元素插入树中可以逐步地生成一棵二叉搜索树。给定一个由不同节点组成的二叉搜索树，输出所有可能生成此树的数组。
示例：
输入：
2
/ \
1 3
输出：
[
[2,1,3],
[2,3,1]
]
解题思路
这是一个困难题目。核心思想是：对于 BST 的每一层，可以选择任意顺序插入该层的节点。使用回溯法，维护一个可选节点列表，每次从中选择一个节点加入结果，然后将其子节点加入可选列表。
Java 代码实现
class Solution {
public List<List<Integer>> BSTSequences(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
result.add(new ArrayList<>());
return result;
}
List<Integer> path = new ArrayList<>();
path.add(root.val);
List<TreeNode> options = new ArrayList<>();
if (root.left != null) options.add(root.left);
if (root.right != null) options.add(root.right);
backtrack(options, path, result);
return result;
}
private void backtrack(List<TreeNode> options, List<Integer> path, List<List<Integer>> result) {
if (options.isEmpty()) {
result.add(new ArrayList<>(path));
return;
}
int size = options.size();
for (int i = 0; i < size; i++) {
TreeNode node = options.get(i);
options.remove(i);
path.add(node.val);
int added = 0;
if (node.left != null) {
options.add(node.left);
added++;
}
if (node.right != null) {
options.add(node.right);
added++;
}
backtrack(options, path, result);
for (int j = 0; j < added; j++) {
options.remove(options.size() - 1);
}
path.remove(path.size() - 1);
options.add(i, node);
}
}
}
面试题 04.10. 检查子树
题目描述
检查子树。你有两棵非常大的二叉树：T1，有几万个节点；T2，有几个节点。设计一个算法，判断 T2 是否为 T1 的子树。如果 T1 中存在从节点 n 开始的子树与 T2 相同，则 T2 为 T1 的子树。
示例 1：
输入：t1 = [1, 2, 3], t2 = [2]
输出：true
解题思路
递归检查：如果 T1 和 T2 的根节点值相同，检查两棵树是否完全相同；否则递归检查 T1 的左子树和右子树。
Java 代码实现
class Solution {
public boolean checkSubTree(TreeNode t1, TreeNode t2) {
if (t2 == null) return true;
if (t1 == null) return false;
if (t1.val == t2.val && isSame(t1, t2)) return true;
return checkSubTree(t1.left, t2) || checkSubTree(t1.right, t2);
}
private boolean isSame(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
if (t1.val != t2.val) return false;
return isSame(t1.left, t2.left) && isSame(t1.right, t2.right);
}
}
面试题 04.12. 求和路径
题目描述
给定一棵二叉树，其中每个节点都含有一个整数数值（该值或正或负）。设计一个算法，打印出任意节点到任意节点（这两个节点不要求是父子关系）之间路径数值和等于给定值的所有路径的数量。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束。
示例：
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回：3。解释：和为 22 的路径有：[5,4,11,2], [5,8,4,5], [4,11,7]
解题思路
使用前缀和技巧。维护一个 Map 记录从根到当前节点路径上的前缀和及其出现次数。对于当前节点，计算当前前缀和，检查是否存在之前的前缀和使得差等于目标值。
Java 代码实现
class Solution {
private int count = 0;
public int pathSum(TreeNode root, int sum) {
Map<Integer, Integer> prefixSum = new HashMap<>();
prefixSum.put(0, 1);
dfs(root, 0, sum, prefixSum);
return count;
}
private void dfs(TreeNode node, int currSum, int target, Map<Integer, Integer> prefixSum) {
if (node == null) return;
currSum += node.val;
count += prefixSum.getOrDefault(currSum - target, 0);
prefixSum.put(currSum, prefixSum.getOrDefault(currSum, 0) + 1);
dfs(node.left, currSum, target, prefixSum);
dfs(node.right, currSum, target, prefixSum);
prefixSum.put(currSum, prefixSum.get(currSum) - 1);
}
}