LeetCode 1373 Maximum Sum BST in Binary Tree

Tag: 二叉搜索树 LeetCode Posted on 2022-02-07 14:43:50 Edited on 2022-02-07 16:12:08 Views: 148

概述

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

这是一道 hard 题。

递归法

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

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

看了一下 labuladong 的教程:

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

  1. 左右子树是否是 BST。
  2. 左子树的最大值和右子树的最小值。
  3. 左右子树的节点值之和。

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

另外这道题有问题,其将 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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/