Home => ProblemSet => 7.1-03:二叉树的直径
1405: 7.1-03:二叉树的直径
Time Limit: 1 Sec Memory Limit: 128 MB Submit: 0 Solved: 0[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]
Description
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
Input
第一行一个整数n，表示结点数
第二行n个数，构成一棵二叉树。-1表示非结点
第二行n个数，构成一棵二叉树。-1表示非结点
Output
一个整数u，表示二叉树的直径
Sample Input Copy
5
1 2 3 4 5
Sample Output Copy
3
HINT
样例一解释:
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
样例二：
左子树高度 + 右子树高度 = 7，而正确答案应该是 8。直径最长路径之一：[1, 0, 6, 8, 9, 7, 6, 9, 2]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
样例二：
左子树高度 + 右子树高度 = 7，而正确答案应该是 8。直径最长路径之一：[1, 0, 6, 8, 9, 7, 6, 9, 2]。
注意：两结点之间的路径长度是以它们之间边的数目表示。