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
| class Solution {
private int ans = 0;
public int diameter(Node root) {
helper(root);
return ans;
}
public int helper(Node node) {
if (node == null) {
return 0;
}
int maxSubTreeHeight = 0, secondMaxSubTreeHeight = 0;
for (Node child : node.children) {
int currSubTreeHeight = helper(child);
if (currSubTreeHeight > maxSubTreeHeight) {
secondMaxSubTreeHeight = maxSubTreeHeight;
maxSubTreeHeight = currSubTreeHeight;
} else if (currSubTreeHeight > secondMaxSubTreeHeight) {
secondMaxSubTreeHeight = currSubTreeHeight;
}
}
ans = Math.max(ans, maxSubTreeHeight + secondMaxSubTreeHeight);
return maxSubTreeHeight + 1;
}
}
|
假设递归函数能够告诉我们某个tree的height. 这就好办了.
时间复杂度: O(n)
空间复杂度: O(n)
