543. 二叉树的直径

Posted on In , Views: Disqus:
LeetCode刷题系列。

描述

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

示例 :

给定二叉树

1
2
3
4
5
6

    1
   / \
  2   3
 / \     
4   5

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

**注意：**两结点之间的路径长度是以它们之间边的数目表示。

来源：力扣（LeetCode）
链接：543. Diameter of Binary Tree

解题思路

根据题意，可以遍历求出经过每个二叉树节点的路径长度，然后从中找到最大值，我们用变量result来保存这个最大值。那么剩下的问题是怎么求这个直径和如何进行遍历。

第一个问题，路径长度的求解，从示例当中可以看出，每个节点的路径长度是这个节点左右子树高度的之和。

第二个问题，节点的遍历通过递归实现，这里需要注意的是，这条路径可能穿过根结点，也可能不经过根节点，所以需要分别对根节点的左右子树递归求值。然后以根节点、左右子节点的路径长度中的最大值来更新result，最后返回，具体代码见解法一。

其实解法一可以进一步优化。

目前在解法一当中一共递归了两次了，在getHeight函数当中递归了一次，然后diameterOfBinaryTree函数也递归了一次，这里可以进行优化，将递归次数减小为一次。

具体代码见解法二。

代码

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int getHeight(struct TreeNode* root)
{
    int left, right, max;
    
    if(root)
    {
        left = getHeight(root->left);
        right = getHeight(root->right);
        max = left > right ? left:right;
        
        return max + 1;
    }
    
    return 0;
}

int max(int a, int b)
{
    if(a > b)
        return a;
    else
        return b;
}

int diameterOfBinaryTree(struct TreeNode* root)
{
    if(!root) return 0;
    
    int result = getHeight(root->left) + getHeight(root->right);
    return max(result, max(diameterOfBinaryTree(root->left), diameterOfBinaryTree(root->right)));
    
}

解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int calMax(struct TreeNode* root, int *result)
{
    if (NULL == root) return 0;
    
    //计算左子树的高度和最大直径
    int left = calMax(root->left, result);
    //计算右子树的高度和最大直径
    int right = calMax(root->right, result);
    
    //更新最大直径
    if (left + right > *result) *result = left + right;
    
    //返回二叉树高度
    return (left > right ? left : right) + 1;
}

int diameterOfBinaryTree(struct TreeNode* root)
{
    int result = 0;
    //需要传result的地址
    calMax(root, &result);
    return result;
}

参考