1522. Diameter of N-Ary Tree

Given a root of an N-ary tree, you need to compute the length of the diameter of the tree.

The diameter of an N-ary tree is the length of the longest path between any two nodes in the tree. This path may or may not pass through the root.

(Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value.)

/*
// 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 {
    int res = 0;
    int depth(Node* node) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for(auto child : node->children) {
            pq.push(depth(child));
            if(pq.size() > 2) pq.pop();
        }
        if(pq.size() == 0) {
            res = max(res, 1);
            return 1;
        } else if(pq.size() == 1) {
            res = max(res, pq.top() + 1);
            return pq.top() + 1;
        } else {
            int second = pq.top(); pq.pop();
            res = max(res, second + pq.top() + 1);
            return pq.top() + 1;
        }
    }
public:
    int diameter(Node* root) {
        depth(root);
        return res - 1;
    }
};