题解 | #树的直径#

树的直径

http://www.nowcoder.com/practice/a77b4f3d84bf4a7891519ffee9376df3

题意整理

给定一棵树，求出这棵树的直径，即树上最远两点的距离。

方法一（dfs）

1.解题思路

首先初始化邻接表，以边的起点为索引，将对应的边的终点以及边的权值放在该索引对应的list里。
先从0号节点进入递归，通过递归找到当前节点所能到达的最远节点，跟新最远节点的规则是路径权值和大于之前的权值和。
然后再从最远节点处继续进入递归体，寻找最大路径权值和。

动图展示： alt

2.代码实现

import java.util.*;

/*
 * public class Interval {
 *   int start;
 *   int end;
 * }
 */

public class Solution {
    /**
     * 树的直径
     * @param n int整型 树的节点个数
     * @param Tree_edge Interval类一维数组 树的边
     * @param Edge_value int整型一维数组 边的权值
     * @return int整型
     */
    //邻接表
    List<List<int[]>> graph;
    //记录最远节点
    long far=0;
    //记录无重复最长路径，即树的直径
    long max=0;
    
    public int solve (int n, Interval[] Tree_edge, int[] Edge_value) {
        //初始化邻接表
        graph=new ArrayList<>();
        for(int i=0;i<n;i++){
            graph.add(new ArrayList<>());
        }
 
        //以边的起点为索引，将对应的边的终点以及边的权值放在list里
        for(int i=0;i<Tree_edge.length;i++){
            graph.get(Tree_edge[i].start).add(new int[]{Tree_edge[i].end,Edge_value[i]});
            graph.get(Tree_edge[i].end).add(new int[]{Tree_edge[i].start,Edge_value[i]});
        }
 
        //从0号节点开始递归
        dfs(0,-1,0);
        max=0;
        //找到最远点后，从当前点递归
        dfs(far,-1,0);
        return (int)max;
    }
    
    //深度优先搜索
    private void dfs(long cur,long pre,long dist){
        //跟新当前最长路径以及最远点
        if(dist>max){
            max=dist;
            far=cur;
        }
        for(int[] child:graph.get((int)cur)){
            //如果没有走回头路，则沿子节点方向递归
            if(child[0]!=(int)pre){
                dfs(child[0],cur,dist+child[1]);
            }
        }
    }
}

3.复杂度分析

时间复杂度：假设树中所有节点个数为n，需要遍历所有的节点，所以时间复杂度是 $O (n)$ 。
空间复杂度：最坏情况下邻接表的大小为 $n^{2}$ ，所以空间复杂度为 $O (n^{2})$ 。

方法二（bfs）

1.解题思路

首先初始化邻接表，以边的起点为索引，将对应的边的终点以及边的权值放在该索引对应的list里。
将0号节点入队，找到当前节点所能到达的最远节点，跟新最远节点的规则是路径权值和大于之前的权值和。如果没有走回头路，将所有可能的子节点入队。
找到最远节点后，继续将最远节点入队，找出最大权值和。

2.代码实现

import java.util.*;

/*
 * public class Interval {
 *   int start;
 *   int end;
 * }
 */

public class Solution {
    /**
     * 树的直径
     * @param n int整型 树的节点个数
     * @param Tree_edge Interval类一维数组 树的边
     * @param Edge_value int整型一维数组 边的权值
     * @return int整型
     */
    //邻接表
    List<List<int[]>> graph;
    //记录最远节点
    long far=0;
    //记录无重复最长路径
    long max=0;
    
    public int solve (int n, Interval[] Tree_edge, int[] Edge_value) {
        //初始化邻接表
        graph=new ArrayList<>();
        for(int i=0;i<n;i++){
            graph.add(new ArrayList<>());
        }
 
        //以边的起点为索引，将对应的边的终点以及边的权值放在list里
        for(int i=0;i<Tree_edge.length;i++){
            graph.get(Tree_edge[i].start).add(new int[]{Tree_edge[i].end,Edge_value[i]});
            graph.get(Tree_edge[i].end).add(new int[]{Tree_edge[i].start,Edge_value[i]});
        }
 
        //初始化队列
        Queue<long[] > queue=new LinkedList<>();
        //从0号节点开始找
        bfs(queue,0,-1,0);
        max=0;
        //找到最远点后，从当前点继续找
        bfs(queue,far,-1,0);
        return (int)max;
    }
    
    //广度优先搜索
    private void bfs(Queue<long[] > queue,long cur,long pre,long dist){
        //加入起始节点到队列
        queue.offer(new long[]{cur,pre,dist});
 
        while(!queue.isEmpty()){
            //取出当前节点信息
            long[] node=queue.poll();
            cur=node[0];
            pre=node[1];
            dist=node[2];
            //如果大于max，则跟新最远距离以及最远节点
            if(dist>max){
                max=dist;
                far=cur;
            }
            for(int[] child:graph.get((int)cur)){
                //如果没有走回头路，则将子节点放入队列
                if(child[0]!=(int)pre){
                    queue.offer(new long[]{child[0],cur,dist+child[1]});
                }
            }
        }
    }
}