LeetCode 1245. 树的直径

2022-08-07 HGNULB 约 10 分钟

文章信息 8 个分类 6 个标签

分类

题目描述

✅ 1245. 树的直径

题意分析

给一棵无向树的边列表，求树的直径——任意两个节点之间最长路径所包含的边数。

输入形式值得注意：给的是无向边而不是父子关系，没有指定根，节点编号从 0 到 n-1，而 n 等于边数加一（这是树的定义决定的：n 个节点恰好 n-1 条边且连通）。所以第一步必然是建无向邻接表，并且不能假设 0 号节点是根。

「树」这个前提给了两条极强的性质：任意两点之间路径唯一，且图连通无环。路径唯一意味着「最短路」和「唯一路径」是同一回事，因此可以用 BFS 求距离；无环意味着遍历时只要不走回头路就不会重复访问。

答案统计的是边数而不是节点数，一条经过 k 个节点的路径长度是 k-1，这个细节直接影响返回值。

边界包括：只有一个节点（edges 为空）时直径是 0；链状树的直径就是 n-1；星形树的直径恒为 2。

解法：两次广度优先搜索

核心思路

暴力做法是从每个节点各跑一次 BFS，取所有最远距离里的最大值，复杂度 $O(n^2)$。它一定正确，但做了大量重复工作——绝大多数起点根本不可能是直径的端点。

关键结论是：从树上任意一点出发，BFS 找到的最远节点，一定是某条直径的端点。因此只需要两次 BFS：第一次从任意节点（比如 0 号）出发定位到一个直径端点 u，第二次从 u 出发，得到的最远距离就是直径。

为什么第一次找到的最远点必然是端点？设某条直径为 (x, y)，从任意起点 s 出发的最远点为 u。若 u 既不是 x 也不是 y，考察 s 到 u 的路径与直径路径的关系：树上路径唯一，两条路径要么相交于某点 m，要么完全不相交。相交时，因为 dist(s,u) >= dist(s,x)，可推出 dist(m,u) >= dist(m,x)，于是把 x 换成 u 得到的路径 (u, y) 长度不小于原直径，说明 u 也是一条直径的端点；不相交的情况在连通树上会导出一条连接两条路径的通道，同样可以推出 dist(m,u) >= dist(m,x)，结论一致。所以用 u 当第二次的起点是安全的。

每次 BFS 内部维护的不变量是：节点第一次被访问时写入的 dist 就是它到起点的距离，且这个距离等于唯一路径上的边数。在树上这一点尤其干净——不存在第二条路径，所以「第一次访问」和「最短路径」天然重合，visited 数组的作用只是防止沿着无向边走回父节点。

BFS 返回两个值：最远节点编号和该节点的距离。第一次调用只用编号，第二次调用只用距离。

解题步骤

由 n = edges.length + 1 算出节点数。这一步用的正是树的定义，不需要扫描边去找最大编号。

建无向邻接表，对每条边 [u, v] 双向各加一次。漏掉一个方向会让树退化成有向图，从某些起点出发根本走不通。

以 0 号节点为起点做第一次 BFS，拿到最远节点 u。起点选谁都行，正是上面那条结论保证的。

以 u 为起点做第二次 BFS，返回的最远距离即为直径。

BFS 内部：用 visited 标记已访问，起点距离为 0；每弹出一个节点就和当前最远节点比较并更新；扩展邻居时，只对未访问的邻居写距离、打标记并入队。

标记必须在入队时立刻打上。树上虽然不会形成环，但无向边会让子节点试图走回父节点，不及时标记就会来回震荡；即便加了「不等于父节点」的判断，入队时标记也是更通用、更不易错的写法。

以 edges = [[0,1],[0,2],[0,3],[2,4],[2,5]] 走一遍。节点数 n = 6，邻接表为：0 连 1、2、3；1 连 0；2 连 0、4、5；3 连 0；4 连 2；5 连 2。这棵树的形状是 0 为中心，挂着叶子 1、3 和一个分支 2，2 下面又挂着 4、5。

第一次 BFS 从 0 出发。dist[0] = 0；弹出 0，扩展得 dist[1] = dist[2] = dist[3] = 1，三者入队；弹出 1，无新邻居（0 已访问），此时 dist[1] = 1 > dist[0] = 0，farthest 更新为 1；弹出 2，dist[2] = 1 不大于 dist[1] = 1，farthest 保持 1，扩展得 dist[4] = dist[5] = 2；弹出 3，距离 1 不更优；弹出 4，dist[4] = 2 > 1，farthest 更新为 4；弹出 5，距离同为 2 不更新。第一次返回最远节点 4，距离 2。

第二次 BFS 从 4 出发。dist[4] = 0；弹出 4，扩展得 dist[2] = 1；弹出 2，扩展得 dist[0] = 2、dist[5] = 2；弹出 0，扩展得 dist[1] = 3、dist[3] = 3；弹出 5，距离 2；弹出 1，dist[1] = 3 成为新的最远；弹出 3，距离同为 3 不更新。最终最远距离是 3。

返回 3。手工核对：路径 4 → 2 → 0 → 1 经过三条边，确实是这棵树上最长的路径；而如果只做一次从 0 出发的 BFS 并直接返回 2，就会漏掉这条跨越中心的路径——这正是必须做两次 BFS 的原因。

代码实现

class Solution {
    public int treeDiameter(int[][] edges) {
        int n = edges.length + 1;
        List<Integer>[] graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] e : edges) {
            graph[e[0]].add(e[1]);
            graph[e[1]].add(e[0]);
        }

        int[] first = bfs(0, graph);
        int[] second = bfs(first[0], graph);
        return second[1];
    }

    private int[] bfs(int start, List<Integer>[] graph) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        int n = graph.length;
        int[] dist = new int[n];
        boolean[] visited = new boolean[n];
        visited[start] = true;

        int farthest = start;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (dist[node] > dist[farthest]) {
                farthest = node;
            }

            for (int next : graph[node]) {
                if (!visited[next]) {
                    visited[next] = true;
                    dist[next] = dist[node] + 1;
                    queue.offer(next);
                }
            }
        }

        return new int[]{farthest, dist[farthest]};
    }
}

func treeDiameter(edges [][]int) int {
    n := len(edges) + 1
    graph := make([][]int, n)
    for _, e := range edges {
        u, v := e[0], e[1]
        graph[u] = append(graph[u], v)
        graph[v] = append(graph[v], u)
    }

    start, _ := bfsTree(0, graph)
    _, dist := bfsTree(start, graph)
    return dist
}

func bfsTree(start int, graph [][]int) (int, int) {
    n := len(graph)
    queue := make([]int, 0)
    queue = append(queue, start)
    visited := make([]bool, n)
    visited[start] = true
    dist := make([]int, n)
    farthest := start
    for head := 0; head < len(queue); head++ {
        node := queue[head]
        if dist[node] > dist[farthest] {
            farthest = node
        }

        for _, next := range graph[node] {
            if !visited[next] {
                visited[next] = true
                dist[next] = dist[node] + 1
                queue = append(queue, next)
            }
        }
    }

    return farthest, dist[farthest]
}

复杂度分析

时间复杂度：$O(n)$，两次 BFS 各自访问每个节点一次、每条边两次，n 个节点 n-1 条边，常数倍的线性扫描。

空间复杂度：$O(n)$，邻接表存 2(n-1) 个方向，dist、visited、队列各占 $O(n)$。

关键点总结

树的直径有两条主流解法：两次 BFS/DFS，和一次树形 DP（对每个节点求「经过它的最长路径 = 最大子树深度 + 次大子树深度」）。两次 BFS 代码最短，树形 DP 更通用——带负权或需要顺便求路径细节时只能用后者。

「从任意点出发的最远点必是直径端点」这条结论必须能证明，面试官几乎必问；证明的抓手是树上路径唯一，把两条路径的交点拿出来做距离比较。

无向图用边列表建图时，两个方向都要加；遍历时靠 visited 或「记录父节点」防止走回头路，前者更通用。

距离统计的是边数还是节点数，要在写第一行代码前就确定；本题起点距离置 0、每扩展一层加一，返回值天然是边数。

面试视角：面试官常追问三处——为什么两次 BFS 就够（给证明）、能不能换成 DFS（可以，但要注意递归深度，链状树上有十万层会栈溢出，BFS 更安全）、如果边有权重会怎样（正权时两次 BFS 换成两次 Dijkstra 或带权 DFS 仍成立，存在负权则该结论失效，必须改用树形 DP）。

易错点总结

错误写法：建图时只加一个方向 graph[e[0]].add(e[1]) → 用例 edges = [[1,0]]，从 0 出发根本走不到 1，两次 BFS 都返回 0，正确答案是 1。

错误写法：只做一次 BFS 就返回最远距离 → 用例 edges = [[0,1],[0,2],[0,3],[2,4],[2,5]]，从 0 出发的最远距离是 2，正确答案是 3。

错误写法：第二次 BFS 仍从 0 出发而不是从第一次的最远点出发 → 用例同上，返回 2 而不是 3。

错误写法：返回第一次 BFS 的距离而不是第二次的 → 用例同上，把 2 当成答案。

错误写法：把节点数写成 edges.length → 用例 edges = [[0,1]]，数组只开 1 格，访问节点 1 时越界异常。

错误写法：出队时才标记 visited → 用例 edges = [[0,1],[0,2]]，节点 1 和 2 会被 0 入队后，又在各自扩展时把 0 重新入队，队列反复震荡，规模膨胀甚至在大图上超时。

错误写法：用「不等于父节点」代替 visited，却在多重边或自环输入上失效 → 本题保证是树可以这样写，但若把同一模板套到含重边的图上，next != parent 挡不住第二条平行边，会死循环。

错误写法：距离数组用「节点数」语义，起点置为 1 → 用例 edges = [[0,1]]，返回 2，正确答案是边数 1。

错误写法：忘记处理 edges 为空的情形而直接访问 edges[0] → 用例 edges = []，单节点树直接抛越界异常，正确答案是 0。

错误写法：用 DFS 递归实现且不控制深度 → 用例是十万节点的链状树，递归深度等于节点数，Java 默认栈直接 StackOverflowError。

错误写法：第二次 BFS 复用第一次的 visited 和 dist 数组而不重置 → 用例 edges = [[0,1],[1,2]]，所有节点都已被标记为已访问，第二次 BFS 一步也扩展不出去，返回 0，正确答案是 2。

错误写法：认为直径必然经过 0 号节点，只在 0 上做「最大深度 + 次大深度」 → 用例 edges = [[0,1],[1,2],[2,3],[1,4],[4,5]]，0 是叶子只有一个分支，算出 3，正确答案是 3 → 2 → 1 → 4 → 5 共 4 条边；「最大加次大」必须对每个节点都取一遍最大值才成立。

相似题目

题目	难度	考察点
543. 二叉树的直径	简单	有根二叉树，用一次后序递归返回深度并在回溯时更新答案
124. 二叉树中的最大路径和	困难	边带权且可为负，回溯时要对负贡献取 0 截断
687. 最长同值路径	中等	路径还需满足节点值相同，向上传递时要判断父子值是否一致
1372. 二叉树中的最长交错路径	中等	路径必须左右交替，状态要带上「上一步往哪边走」
310. 最小高度树	中等	求的是直径的中点，用拓扑式地逐层剥叶子直到剩一两个节点
剑指 Offer 55 - I. 二叉树的深度	简单	只需单侧最大深度，是直径类问题的最小组成部件