二叉树最大和

Posted on Edited on Symbols count in article: 1.9k Reading time ≈ 2 mins.

1. 124 二叉树中的最大路径和

1.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
class Solution {
public:
    int ans = INT_MIN;
    int core(TreeNode* root) { // 找到以root为起点，深入向下的最大路径一条线（分叉只走一条）
        if(!root) return 0;
        int lv = core(root->left);
        int rv = core(root->right);
        int res = max(max(lv, rv), 0) + root->val;
        return res;
    }
    
    void recursion(TreeNode* root){ // 遍历树中每个结点，尝试寻找本题答案的“起点根”
        if(!root) return;
        recursion(root->left);
        recursion(root->right);
        int lv = core(root->left); // 以左孩子为起点的“线”
        int rv = core(root->right); // 以右孩子为起点的“线”
        if(lv < 0) lv = 0;
        if(rv < 0) rv = 0;
        ans = max(ans, lv + rv + root->val);
    }
    
    int maxPathSum(TreeNode* root) {
        recursion(root);
        return ans;
    }
};

1.2 一个递归的好方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int ans = INT_MIN;
    int core(TreeNode* root) {
        if(!root) return 0;
        
        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int lv = max(core(root->left), 0);
        int rv = max(core(root->right), 0);
        
        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int ifAnsRoot = root->val + lv + rv;
        ans = max(ans, ifAnsRoot);
        
        // 返回
        return max(lv, rv) + root->val;
    }
    
    int maxPathSum(TreeNode* root) {
        core(root);
        return ans;
    }
};

2. 543 二叉树的直径

这些问题都有共性：递归主线依旧，所求是副产物

2.1 两个递归的笨方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int core(TreeNode* root){
        if(!root) return 0;
        int l = core(root->left);
        int r = core(root->right);
        return max(l, r) + 1;
    }
    
    int diameterOfBinaryTree(TreeNode* root) {
        if(!root) return 0;
        int l = diameterOfBinaryTree(root->left);
        int r = diameterOfBinaryTree(root->right);
        int m = core(root->left) + core(root->right);
        return max(m, max(l, r));
    }
};

2.2 一个递归的好方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 递归主线还是算高度，直径是 [副产品]
class Solution {
public:
    int res = 0;
    int core(TreeNode* root){ // 给定根节点，计算最长深度节点数
        if(!root) return 0;
        int l = core(root->left); // 左儿子为根的子树的深度
        int r = core(root->right); // 右儿子为根的子树的深度
        res = max(res, l + r); // 在这里更新res，不用+1，因为路径长度是总结点长度-1
        return max(l, r) + 1; // 返回该节点为根的子树的最长深度节点数
    }
    
    int diameterOfBinaryTree(TreeNode* root) {
        if(!root) return 0;
        core(root);
        return res;
    }
};