树的直径

题目描述

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

包含n个结点，n-1条边的连通图称为树。

示例1的树如下图所示。其中4到5之间的路径最长，是树的直径，距离为5+2+4=11

示例1

输入

复制

6,[[0,1],[1,5],[1,2],[2,3],[2,4]],[3,4,2,1,5]

返回值

复制

11

通用解法

对于此类问题，我们需要构建图来做深度优先搜索。

• 首先，根据父子关系及边权重构建无向图；

• 然后，随机找一顶点，利用深度优先搜索找到距离该点最远的顶点remote。

• 最后，从remote顶点开始深度优先搜索找到最长路径，该路径即为直径。

巧妙解法

我们记录每个节点向下，所能延伸的最远距离 $d_1$，和次远距离$d_2$ ，那么直径就是所有$d_1+d_2$ 的最大值。

import java.util.*;
public class Solution {
    public int solve (int n, Interval[] Tree_edge, int[] Edge_value) {
        List<Node> [] edges = new List[n];
        for(int i=0;i<n;i++){
            edges[i] = new ArrayList<>();
        }
        // 建立邻接表无向图
        for(int i=0;i<Tree_edge.length;i++){
            edges[Tree_edge[i].start].add(new Node(Tree_edge[i].end,Edge_value[i]));
            edges[Tree_edge[i].end].add(new Node(Tree_edge[i].start,Edge_value[i]));
        }
        dfs(edges,Tree_edge[0].start,-1);
        return max;
    }
    
    int max = 0;
    
    public int dfs(List<Node> []edges,int curr,int parent){
        int maxDepth = 0;
        int secondDepth = 0;
        for(Node node:edges[curr]){
            if(node.id == parent)continue;
            int depth = node.weight + dfs(edges,node.id,curr);
            if (depth > maxDepth) {
                secondDepth = maxDepth;
                maxDepth = depth;
            }else if (depth > secondDepth) {
                secondDepth = depth;
            }
            maxDepth = Math.max(maxDepth,depth);
        }
        max = Math.max(max,maxDepth+secondDepth);
        return maxDepth;
    }
    
    private class Node {
        int id;
        int weight;
        public Node(int id,int weight){
            this.id = id;
            this.weight = weight;
        }
    }
}

参考文献

树的直径 - OI Wiki (oi-wiki.org)

赏

谢谢你请我吃糖果

微信