🧠 第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 与框架中的应用

📌 四、总结 Summary

• 树结构用于分层表达、层级遍历、祖先查找等问题。
• 图结构用于最短路径、传递闭包、依赖分析等问题。
• 常用算法包括 BFS/DFS/Dijkstra/拓扑排序 等，掌握 Java 实现是通关面试的关键！