leetcode543--二叉树的直径

1. 题意

求二叉树上最远两个节点之间的距离。

2. 题解

2.1 暴力

最长路径的三种情况

• 通过根节点
• 在左子树
• 在右子树

            1
         2    
     4     5  
  6  7   8   9 
  diameter =  5
1
2
3
4
5

通过根节点的最长路径长度一定是左右子树深度之和。

但是这样求左右子树的深度会不断重复，所以复杂度很高。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int getDepth(TreeNode *root) {
        return root == nullptr ? 0 : max(getDepth(root->left), getDepth(root->right)) + 1;
    }

    int diameterOfBinaryTree(TreeNode* root) {

// 最长路径的三种情况
// * 通过根节点
// * 在左子树
// * 在右子树

//          1
//       2    
//     4  5  
//  6 7  8 9
// diameter =  5
        if ( nullptr == root)
            return 0;
        
        int lmx = diameterOfBinaryTree(root->left);
        int rmx = diameterOfBinaryTree(root->right);

        int ans = max(lmx, rmx);
        int ldepth = getDepth(root->left);
        int rdepth = getDepth(root->right);


        return max(ans, ldepth + rdepth); 
    }
};
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
42
43

2.2 动态规划

我们可以在求深度的时候，更新答案，返回经过根节点但不拐弯的链的最长长度。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 自底向上求出，经过当前节点的最大深度
    // 并统计经过当前节点的路径长度
    // 返回经过子树的深度

    int getDepth(TreeNode *root, int &ans) {
        if ( nullptr == root)
            return 0;
        int ldepth = getDepth(root->left, ans);
        int rdepth = getDepth(root->right, ans);

        ans = max( ldepth + rdepth + 1, ans);
        
        return max(ldepth, rdepth) + 1;
    }

    int diameterOfBinaryTree(TreeNode* root) {
        int ans = 0;

        getDepth(root, ans);
        
        return ans - 1;
    }
};
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