Leetcode 1522. Diameter of N-Ary Tree (python+cpp)

题目：

解法：

这是543的follow up，解法几乎是一样的，只不过左子树和右子树的深度替换成所有子树里面深度最大的两个

class Solution:def diameter(self, root: 'Node') -> int:""":type root: 'Node':rtype: int"""def get_depth(node):nonlocal diameterlargest = 0sec_largest = 0for child in node.children:d = get_depth(child)if d>largest:sec_largest = largestlargest = delif d>sec_largest:sec_largest = ddiameter = max(diameter,largest+sec_largest)return max(largest,sec_largest)+1diameter = 0get_depth(root)return diameter

C++

class Solution {
    int ans;
public:int diameter(Node* root) {
    ans = 0;get_depth(root);return ans;}int get_depth(Node* node){
    if (!node) return 0;int largest = 0;int sec_largest = 0;for (auto child:node->children){
    int d = get_depth(child);if (d>largest){
    sec_largest = largest;largest = d;}else if (d>sec_largest){
    sec_largest = d;}}ans = max(ans,largest+sec_largest);return max(largest,sec_largest)+1;}
};