Diameter of Binary Tree

LeetCode
,

第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
     / \
    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.

很显然，题目已经给出提示了,这个path要么经过root要么不经过root.

如果经过root,那么就是左子树和右子树的高度之和加上2.
如果不经过root,就是左子树的diameter或者是右子树的diameter.

那么如何分辨是否经过root呢？

其实也很简单，反正就要求最大的嘛，我们就把两种情况都算一遍，然后求个max即可。大概可以写出一下递推式：

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int diameterOfBinaryTree(TreeNode* root) {
    int h;
    return diameterOfBinaryTree(root,h);
}
int diameterOfBinaryTree(TreeNode *root,int &height) {
    if (root == nullptr) {
        height = -1;
        return 0;
    }
    int leftH,rightH;
    int leftD = diameterOfBinaryTree(root->left,leftH);
    int rightD = diameterOfBinaryTree(root->right,rightH);

    height = max(leftH,rightH) + 1;
    return max(leftH + rightH + 2,max(leftD,rightD) );
}