<div>
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:
<pre>Input: root = [1,null,3,2,4,null,5,6] Output: 3 Explanation: Diameter is shown in red color.</pre>
Example 2:
<pre>Input: root = [1,null,2,null,3,4,null,5,null,6] Output: 4 </pre>
Example 3:
<pre>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 </pre>
Constraints:
- The depth of the n-ary tree is less than or equal to
1000. - The total number of nodes is between
[1, 10<sup>4</sup>].
</div>
题目大意：
求树的直径：任何两个节点的最大距离
解题思路：
类似于LeetCode 543 Diameter of Binary Tree，但此题为N叉树
解题步骤：
DFS
注意事项：
- 求数组中最大的两数和，用去掉最大值的方法得到次大值。还要注意初始值加入[1, 1]，避免没有儿子节点或只有一个的情况
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19def diameter(self, root: 'Node') -> int:
max_len = 0
def dfs(root):
if not root:
return 0
nonlocal max_len
path_len = [1, 1]
for child in root.children:
path_len.append(dfs(child) + 1)
largest = max(path_len)
path_len.remove(largest)
second_largest = max(path_len)
total = largest + second_largest - 1
max_len = max(total, max_len)
return largest
dfs(root)
return max_len - 1
算法分析：
时间复杂度为O(n)，空间复杂度O(n)
