---
tags: leetcode
---

# [1522. Diameter of N-Ary Tree](https://leetcode.com/problems/diameter-of-n-ary-tree/)
---
# My Solution
## The Key Idea for Solving This Coding Question
## C++ Code

/*
// 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) {
        int answer = 0;

        dfs(root, answer);
        return answer;
    }

private:
    int dfs(Node *root, int &answer) {
        if (root == nullptr) {
            return 0;
        }

        // long1 > long2
        int long1 = 0, long2 = 0;
        for (Node *next : root->children) {
            int tmp = dfs(next, answer);
            if (tmp > long1) {
                // tmp > long1 > long2
                long2 = long1;
                long1 = tmp;
            } else if (tmp > long2) {
                // long1 > tmp > long2
                long2 = tmp;
            }
        }

        int max1 = max(long1, long2);
        int max2 = max(max1, long1 + long2);
        answer = max(answer, max2);

        return max1 + 1;
    }
};

## Time Complexity
$O(n)$
$n$ is the number of nodes in the n-ary tree referred by `root`.
## Space Complexity
$O(H)$
$H$ is the hight of the n-ary tree referred by `root`.
# Miscellane
<!--
# Test Cases

[1,null,3,2,4,null,5,6]

[1,null,2,null,3,4,null,5,null,6]

[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]

-->