X

LEETCODE 1245. Tree Diameter 解题思路分析

题目大意:

树的直径

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

树用一个数组给出,数组为 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-解题思路分析/
Categories: leetcode
kwantong:

View Comments (6)

  • 可以优化一下,只有edge为1的点到另一个edge的点可以产生最大长度。所以不用判断所有点,开始遍历一遍edge number。

  • 谢谢你的分享!可以分析一下这个解法的复杂度吗?我认为时间复杂度是O(N) 因为每一条边都需要访问一遍;空间复杂度最坏情况也是O(N),最坏情况是整个树实际上是一条链表。

    • 感谢你的回复,希望能和你多多交流。

      时间复杂度:
      dfs需要遍历每一个节点,由于不会重复遍历,所以这一部分的时间复杂度是O(N),除此之外查找所有顶点的邻接点所需时间为O(E),E为所有边的数量。固精确来讲,dfs总的时间复杂度应该是O(N+E)

      空间复杂度:
      由于我们需要建立树形结构(List[] tree),空间复杂度是O(N)。
      另外dfs本身是递归,它的空间复杂度也是O(N)。

      如有不对,还请指教