Description
Given
a binary tree, you need
to compute
the length of the diameter
of the tree. The diameter
of a
binary tree is
the length of the longest path between
any two nodes
in a tree. This path may
or may
not pass through
the root.
Example
Given
a binary tree
1
/ \
2 3
/ \
4 5
Return
3, which is
the length of the path [
4,
2,
1,
3]
or [
5,
2,
1,
3].
Note
The
length of path
between two nodes
is represented
by the number of edges
between them.
Solution 1(C++)
class Solution {
public:
int maxdiadepth =
0;
int dfs(TreeNode* root){
if(root == NULL)
return 0;
int leftdepth = dfs(root->left);
int rightdepth = dfs(root->right);
if(leftdepth + rightdepth > maxdiadepth) maxdiadepth = leftdepth + rightdepth;
return max(leftdepth +
1, rightdepth +
1);
}
int diameterOfBinaryTree(TreeNode* root) {
dfs(root);
return maxdiadepth;
}
};
算法分析
这一道题，其实就是要计算一个树的最大深度。其实这里的dfs应该不算严格意义上的深度优先，更像是递归。这段代码改写一下也就可以求树的最大深度。经典题目。
程序分析
参考资料：二叉树最大深度和最小深度。
树的最大深度代码：
int maxDepth(TreeNode
*root) {
if(!root)
return 0;
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return leftDepth > rightDepth ? (leftDepth +
1) : (rightDepth +
1);
}
树的最小深度代码：
int minDepth(TreeNode
*root) {
if(root
== NULL)
return false;
if(root
->left
== NULL)
return minDepth(root
->right)
+ 1;
if(root
->right
== NULL)
return minDepth(root
->left)
+ 1;
int leftDepth
= minDepth(root
->left);
int rightDepth
= minDepth(root
->right);
return leftDepth
< rightDepth
? (leftDepth
+ 1) : (rightDepth
+ 1);
}
