LeetCode 1373 Maximum Sum BST in Binary Tree

    
        标签：
        
            二叉搜索树
        
            LeetCode
        
    发布于：2022-02-07 14:43:50
    编辑于：2022-02-07 16:12:08
    浏览量：800

概述

https://leetcode.com/problems/maximum-sum-bst-in-binary-tree/

这是一道 hard 题。

递归法

这里比较麻烦的一点是，判断子树是否为合法的 BST 时，我们还得区分全局范围和本地范围。

好麻烦，hard 果然是 hard，哭了。

看了一下 labuladong 的教程：

站在当前节点的视角，需要知道以下具体信息：

左右子树是否是 BST。

左子树的最大值和右子树的最小值。

左右子树的节点值之和。

有一点要注意啊，因为值可能为负数，所以我们必须存一个全局变量来记录最大值，否则传到根节点后其可能反而会变小。

另外这道题有问题，其将 nullptr 也视为 BST。

class Solution {
public:
    int ans = INT_MIN;
    int maxSumBST(TreeNode* root) {
        helper(root);
        if (ans < 0) return 0;  // this question is weird
        return ans;
    }
    
    vector<int> helper(TreeNode* root) {
        vector<int> res(4, 0);  // isBST, maxSumBST, maxValue, minValue
        if (!root) {
            res[0] = 1;
            res[1] = INT_MIN;
            res[2] = INT_MIN;
            res[3] = INT_MAX;
            return res;
        }
        auto lres = helper(root->left);
        auto rres = helper(root->right);
        bool isBST = lres[0] == 1 && rres[0] == 1 && root->val > lres[2] && root->val < rres[3];
        if (isBST) {
            res[0] = 1;
            res[1] = root->val;
            if (root->left) res[1] += lres[1];
            if (root->right) res[1] += rres[1];
            ans = max(ans, res[1]);
        } else {
            res[0] = 0;
            res[1] = max(lres[1], rres[1]);
        }
        res[2] = max(root->val, max(lres[2], rres[2]));
        res[3] = min(root->val, min(lres[3], rres[3]));
        
        return res;
    }
};

Links: leetcode-1373-maximum-sum-bst-in-binary-tree