Diameter of N-Ary Tree

给一个n-ary的树, 求周长. 就是任意两个node之间的最长距离, 可以不经过root.

最长的路径出现在两个情况, 情况一是路径经过node, 那么就是左右两边的最长路径相加, 要不然就是一侧,就是最长路径. 所以要求出最长路径和次长路径, 然后比较一下.

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
     int res = 0;
     int dfs(Node* root) {
        if (!root) 
            return 0;
        vector<int> v;
        for (auto &c: root->children) {
            v.push_back(f(c));
        }
         sort(v.begin(), v.end(), greater<int>());
        auto l1 = 0, l2 = 0;
         int n = v.size();
         if(n > 0){
             l1 = v[0];
         }
         if(n > 1){
             l2 = v[1];
         }
        res = max(res, l1 + l2);
        return 1 + max(l1, l2);
    }
    
    int diameter(Node* root) {
        dfs(root);
        return res;
    }
    
};