05 August 2008
N-ary树的直径，直径是两个最远的nodes的距离
In this solution, we are exploring all nodes of the input N-Ary Tree using Depth-First Search.
Length of the longest path passing through a node = 1st Max Height among N children + 2nd Max Height among N children + 2
Thus, Diameter of the entire tree = Max(Length of the longest path passing through each node)
Complexity Analysis:
For complexity calculation, let us assume:
N = Maximum number of children of a node. Each node can have 0 to N nodes.
M = Total number of nodes in the input N-Ary Tree.
Time Complexity:
In a Tree, if there are M nodes, then there will be M-1 edges.
In this solution, each node and each edge will be visited once.
Thus, Total Time Complexity = O(V + E) = O(M + M-1) = O(M)
Space Complexity: O(Height of the input tree)
In worst case, for a skewed tree, height can be equal to the total number of nodes. Thus, worst case space complexity = O(M)
In best / average case, for a balanced N-ary tree, height = O(log M / log N) = O(logN M).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public int diameter(Node root) {
if (root == null || root.children.size() == 0) {
return 0;
}
int[] maxD = new int[1];
dfs(root, maxD);
return maxD[0];
}
private int dfs(Node root, int[] maxD) {
if (root.children.size() == 0) {
return 0;
}
// Setting below maximums to -1 helps in the case if there is only one child
// node of this root node.
int maxHeight1 = -1;
int maxHeight2 = -1;
for (Node child : root.children) {
int childHeight = dfs(child, maxD);
if (childHeight > maxHeight1) {
maxHeight2 = maxHeight1;
maxHeight1 = childHeight;
} else if (childHeight > maxHeight2) {
maxHeight2 = childHeight;
}
}
maxD[0] = Math.max(maxD[0], maxHeight1 + maxHeight2 + 2);
return maxHeight1 + 1;
}
}