関小君刷题记

题目大意：

树的直径

给定一棵无向树，返回它的直径：树中最长路径的 边 的数量。

树用一个数组给出，数组为 edges[i] = [u, v]，每个元素代表一条双向边连接结点 u 和 v。每个结点的编号为 {0, 1, …, edges.length}。

示例 1：

Input: edges = [[0,1],[0,2]]
Output: 2
Explanation: 
A longest path of the tree is the path 1 - 0 - 2.

示例 2：

Input: edges = [[0,1],[1,2],[2,3],[1,4],[4,5]]
Output: 4
Explanation: 
A longest path of the tree is the path 3 - 2 - 1 - 4 - 5.

提示：

• 0 <= edges.length < 10^4
• edges[i][0] != edges[i][1]
• 0 <= edges[i][j] <= edges.length
• edges 会形成一棵无向树。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1245

解题思路分析：

遇到树的题目，多数要考虑到使用dfs或者bfs来解题。本题也不例外，从任意一点开始dfs整棵树，对于任意当前节点，它能组成的最大边长应该是从自身出发的所有路径中最长两条路径长度的和。因此，在每一步dfs中，我们需要记录下当前节点最长两条路径的长度，并求出和sum。同时返回最长的一条边的长度给上层dfs。全部dfs结束后，找到最大的sum即是结果。

看下实现代码：

int res=0; // 返回结果
public int treeDiameter(int[][] edges) {
    // 利用边的信息构建出树的结构，即每个节点能和哪些节点相连接
    List<Integer>[] tree = new List[edges.length+1];
    // 初始化
    for(int i=0;i<tree.length;i++){
        tree[i] = new ArrayList<>();
    }
    // 构建树
    for(int[] edge : edges){
        tree[edge[0]].add(edge[1]);
        tree[edge[1]].add(edge[0]);
    }
    dfs(tree, 0, -1); // 开始dfs
    return res;
}
// tree为树的结构图
// current为当前节点
// previous为前一个节点
// 返回值为：以当前节点为起点的一条最大路径长度
int dfs(List[] tree, int current, int previous){
    // 查看当前节点能与哪些节点连接
    List<Integer> list = tree[current];
    int max1=0; // 以当前节点为起点的一条最大路径长度
    int max2=0; // 以当前节点为起点的一条次大路径长度
    // 循环所有与当前节点相连的点
    for(int next : list){
        // 防止走回头路
        if(next != previous){
            // dfs得到下一个节点一条路径的最大长度
            // 加一之后为当前节点一条路径的长度
            int max = dfs(tree, next, current)+1;
            // 比较当路径长度与之前得到的max1，max2，并更新最大值
            if(max>=max1){
                max2=max1;
                max1=max;
            }else if(max>=max2){
                max2=max;
            }
            // max1+max2得到当前节点最大边长,与返回结果比较，更新最大值
            res=Math.max(res, max1+max2);
        }
    }
    // 返回当前节点一条路径的最大长度
    return max1;
}

本题解法执行时间为7ms。

Runtime: 7 ms, faster than 93.75% of Java online submissions for Tree Diameter.

Memory Usage: 46.6 MB, less than 100.00% of Java online submissions for Tree Diameter.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1245-tree-diameter-解题思路分析/