1522. Diameter of N-Ary Tree

postorder O(n) time O(h) space
需要考虑的几个case

1. nullptr
2. single node
3. 其他

/*
// 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 diameter(Node* root) {
        dfs(root);
        return res;
    }

    int dfs(Node *root) {
        if (!root) return 0;
        int mx = 0, submx = 0;
        for (auto child : root->children) {
            int len = dfs(child) + 1; // 这里+1可以更好的表示边的概念
            if (len > mx) {
                submx = mx;
                mx = len;
            } else if (len > submx) {
                submx = len;
            }
        }
        res = max(res, mx + submx);
        return mx;
    }

    int res = 0;
};