第58天。
今天的题目是Diameter of Binary Tree:
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 12 / \3 2 34 / \5 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.
很显然,题目已经给出提示了,这个path要么经过root
要么不经过root
.
如果经过root
,那么就是左子树和右子树的高度之和加上2.
如果不经过root
,就是左子树的diameter
或者是右子树的diameter
.
那么如何分辨是否经过root
呢?
其实也很简单,反正就要求最大的嘛,我们就把两种情况都算一遍,然后求个max
即可。大概可以写出一下递推式:
1leftH = heightOfHeight(root->left)2rightH = heightOrHeight(root->right)3d = diameterOfBinaryTree(root->left) + diameterOfBinaryTree(root->right)4return max(d,leftH+rightH+2)
然后我们发现求高度也是类似的需要递归的方式,所以我们可以将他们合并起来:
1int diameterOfBinaryTree(TreeNode* root) {2 int h;3 return diameterOfBinaryTree(root,h);4}5int diameterOfBinaryTree(TreeNode *root,int &height) {6 if (root == nullptr) {7 height = -1;8 return 0;9 }10 int leftH,rightH;11 int leftD = diameterOfBinaryTree(root->left,leftH);12 int rightD = diameterOfBinaryTree(root->right,rightH);13
14 height = max(leftH,rightH) + 1;15 return max(leftH + rightH + 2,max(leftD,rightD) );1 collapsed line
16}