题解 | #树的直径#

后序遍历
(1)跟[二叉树的最大路径和]一个思路，不同的是这里树不一定是二叉;
(2)注意，起始根结点不一定是0，只要是叶子节点都可以作为根结点进行计算，另外边也不一定是从父节点到子节点，看用什么做根，所以邻接表需要无向边，而不是有向边。

/**
 * struct Interval {
 *    int start;
 *    int end;
 * };
 */

class Solution {
public:
    struct Node{
        int v;
        int dis;
        Node(int _v, int _dis):v(_v), dis(_dis){}
    };
    int ans = 0;
    int start; //根结点
    vector<vector<Node>> Adj;
    /**
     * 树的直径
     * @param n int整型 树的节点个数
     * @param Tree_edge Interval类vector 树的边
     * @param Edge_value int整型vector 边的权值
     * @return int整型
     */
    int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
        // write code here
        Adj.resize(n);
        for(int i = 0; i < n - 1; i ++){
            int u = Tree_edge[i].start, v = Tree_edge[i].end;
            int dis = Edge_value[i];
            Adj[u].push_back(Node(v, dis));
            Adj[v].push_back(Node(u, dis));
        }

        for(int i = 0; i < n; i ++){ //找起始点
            if(Adj[i].size() == 1){
                start = i;
                break;
            }
        }
        postOrder(start, -1);
        return ans;
    }
    int postOrder(int u, int parent){
        if(Adj[u].size() == 1 && u != start) return 0;
        vector<int> vec;
        for(int i = 0; i < Adj[u].size(); i ++){
            int v = Adj[u][i].v, dis = Adj[u][i].dis;
            if(v == parent) continue;
            int dist = postOrder(v, u) + dis;
            vec.push_back(dist);
        }
        sort(vec.begin(), vec.end());
        int n = vec.size();
        ans = max(ans, vec[n - 1] + (n > 1 ? vec[n - 2] : 0));
        return vec[n - 1];
    }
};