Code & Func

第58天。

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

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即可。大概可以写出一下递推式：

1
leftH = heightOfHeight(root->left)
2
rightH = heightOrHeight(root->right)
3
d = diameterOfBinaryTree(root->left) + diameterOfBinaryTree(root->right)
4
return max(d,leftH+rightH+2)

然后我们发现求高度也是类似的需要递归的方式，所以我们可以将他们合并起来：

1
int diameterOfBinaryTree(TreeNode* root) {
2
    int h;
3
    return diameterOfBinaryTree(root,h);
4
}
5
int 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
}