🧠 第6天：树与图深度剖析——高频算法面试题 & Java 实战
📚 一、核心知识概览 Overview
1. 树（Tree）
树是一种非线性数据结构，常见于面试中的二叉树（Binary Tree）、二叉搜索树（BST）、N叉树等。
常见面试考点：
- 树的遍历（前序、中序、后序、层序）
- 最近公共祖先（Lowest Common Ancestor, LCA）
- 判断平衡树、对称树、二叉搜索树验证等
2. 图（Graph）
图是一种更复杂的数据结构，常用于建模复杂关系，如社交网络、地图、网络延迟等。
常见面试考点：
- 图的表示（邻接表 / 邻接矩阵）
- BFS / DFS 遍历
- 拓扑排序、最短路径（Dijkstra、Floyd）、网络延迟
🧩 二、算法实战 Algorithms & Java 实现
🌟 案例1：二叉树的层序遍历（Level Order Traversal）
💬 题目描述
给你一棵二叉树，请你返回其按层序遍历得到的节点值。
✅ 示例输入
Input: [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
🔍 解法：BFS（队列实现）
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 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);}result.add(level);}return result;
}
🌟 案例2：二叉树的最近公共祖先（Lowest Common Ancestor）
💬 题目描述
给定一棵二叉树，找到两个节点的最近公共祖先。
✅ 示例输入
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
🔍 解法：递归 + 后序遍历
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;
}
🌟 案例3：网络延迟时间（Network Delay Time）
💬 题目描述
给定一个有向图，每条边由三元组 (u, v, w) 表示从节点 u 到 v 的路径时间为 w，返回从源节点 K 发出信号，到所有节点的最短时间。
✅ 示例输入
Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2
🔍 解法：Dijkstra 算法（优先队列实现最短路径）
public int networkDelayTime(int[][] times, int N, int K) {Map<Integer, List<int[]>> graph = new HashMap<>();for (int[] time : times) {graph.computeIfAbsent(time[0], k -> new ArrayList<>()).add(new int[]{time[1], time[2]});}int[] dist = new int[N + 1];Arrays.fill(dist, Integer.MAX_VALUE);dist[K] = 0;PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));pq.offer(new int[]{K, 0});while (!pq.isEmpty()) {int[] cur = pq.poll();int u = cur[0], time = cur[1];if (time > dist[u]) continue;if (!graph.containsKey(u)) continue;for (int[] next : graph.get(u)) {int v = next[0], w = next[1];if (dist[v] > dist[u] + w) {dist[v] = dist[u] + w;pq.offer(new int[]{v, dist[v]});}}}int max = Arrays.stream(dist).skip(1).max().getAsInt();return max == Integer.MAX_VALUE ? -1 : max;
}
🛠 三、JDK 与框架中的应用
| 数据结构 | 应用场景 | 框架示例 |
|---|---|---|
| Tree | TreeMap、TreeSet、BinaryTree 实现 | Java Collection Framework |
| Graph | 服务依赖图、任务拓扑排序 | Spring Boot AutoConfig、微服务拓扑 |
📌 四、总结 Summary
- 树结构用于分层表达、层级遍历、祖先查找等问题。
- 图结构用于最短路径、传递闭包、依赖分析等问题。
- 常用算法包括 BFS/DFS/Dijkstra/拓扑排序 等，掌握 Java 实现是通关面试的关键！
