题解 | #树的直径#

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

案例
输入：6,[[0,1],[1,5],[1,2],[2,3],[2,4]],[3,4,2,1,5]
返回值：11
案例说明:
选择4点到5点的距离,距离为5+2+4=11，为距离最长

方法一 树上dp

1.对一颗树从叶子结点向根遍历
2.遍历到每个点时记录该点到叶子结点的最大值与次大值
3.对于每次取的最大值与次大值相加取最大就是答案

class Solution {
public:
    unordered_map<int, vector<pair<int,int> >> G;
    int ans = 0;
    int mx[100010], cm[100010];//最大值与次大值
    int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
        // write code here
        for(int i = 0; i < n - 1; i ++){ //存图
            G[Tree_edge[i].start + 1].push_back({Tree_edge[i].end + 1, Edge_value[i]});
            G[Tree_edge[i].end + 1].push_back({Tree_edge[i].start + 1, Edge_value[i]});
            mx[i + 1] = cm[i + 1] = 0;
        }
        dfs(1, 0);
        return ans;
    }
    void dfs(int now, int fa){
        cm[now] = mx[now] = 0;
        for(auto [to, v]: G[now]){ // 与当前点相连的点
            if(to == fa) continue;
            dfs(to, now);
            int vs = mx[to] + v; 
            if(vs > mx[now]){ //更新最大值
                cm[now] = mx[now]; //将上一个最大值赋予次大值
                mx[now] = vs;
            }else if(vs > cm[now]) cm[now] = vs; //更新次大值
        }
        ans = max(ans, mx[now] + cm[now]); 
    }
};

时间复杂度: 遍历整颗树
空间复杂度: 存储整颗树,以及递归调用栈的空间为树的深度

方法二 dfs

先从任意一点出发找到离它最远的一个直径点x，再从找到的最远直径点x出发找到离当前点最远的直径点y,这样x到y就是这个树上的直径。

class Solution {
public:
    unordered_map<int, vector<pair<int,int> >> G;
    int ans = 0, ed = 0;
    int  vis[100010]; //存储点是否到达过
    int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
        // write code here
        for(int i = 0; i < n - 1; i ++){ //存图
            G[Tree_edge[i].start + 1].push_back({Tree_edge[i].end + 1, Edge_value[i]});
            G[Tree_edge[i].end + 1].push_back({Tree_edge[i].start + 1, Edge_value[i]});
        }
        dfs(1, 0, 0); //从任意点招到最远权值点ed
        memset(vis, 0, sizeof vis);
        dfs(ed, 0, 0);//ed点开始招最大直径
        return ans;
    }
    void dfs(int now, int fa, int sum){
        for(auto [to, v]: G[now]){ 
            if(to == fa || vis[to]) continue;
            vis[to] = 1;
            dfs(to, now, sum + v); 
        }
        if(ans < sum){ //找到的点大于已发现的点则更新答案
            ans = sum; ed = now;
        }
    }
};

时间复杂度: 遍历整颗树
空间复杂度: 存储整整颗树,以及递归调用栈的空间为树的深度