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.)
Example 1:
Input: root = [1,null,3,2,4,null,5,6]
Output: 3
Explanation: Diameter is shown in red color.
Example 2:
Input: root = [1,null,2,null,3,4,null,5,null,6]
Output: 4
Example 3:
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null
,null,11,null,12,null,13,null,null,14]
Output: 7
Constraints:
The depth of the n-ary tree is less than or equal to 1000.
The total number of nodes is between [0, 10^4].
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/diameter-of-n-ary-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
/*
// 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 ans = 0;
public:
int diameter(Node* root) {
h(root);
return ans;
}
int h(Node* root)
{
if(!root) return 0;
int maxdep1 = 0, maxdep2 = 0, height;
for(auto c : root->children)
{
height = h(c);
if(height >= maxdep1)
{
maxdep2 = maxdep1;
maxdep1 = height;
}
else if(height > maxdep2)
maxdep2 = height;
}
ans = max(ans, maxdep2+maxdep1);
return max(maxdep1, maxdep2) + 1;
}
};
32 ms 10.7 MB