ARST打卡第211周[211/521]

发表于 2023-05-20 分类于 ARST 阅读次数：

lc1373_二叉搜索子树的最大键值和【TED演讲】拖延症人的内心世界理解LSM Tree_一种高效读写的存储引擎感谢耗子叔，永远怀念耗子叔

Algorithm

lc1373_二叉搜索子树的最大键值和

思路:
贪心递归回溯每一个子节点是否是搜索二叉树，是的话贪心维护最大值

贪心回溯不好用中序遍历，因为中序遍历最后不是遍历根，如何让中序遍历返回根？
或者用后序遍历，但是要最终判断左孩子比自己小，右孩子比自己大 – 这个比中序遍历好实现一点
判断是二叉搜索树之后再求和，那会导致时间复杂度到 O($n^2$)，会超时
所以需要遍历的时候就记录，直接给每个节点加一个sum值，是否是二叉搜索树bool的属性就是递归回溯了，嗯嗯

数据范围16*1e8不会爆int

思路应该是对的，但是好久没写了，手生，先学习一下题解吧，嗯嗯

与题解的差距:
理解小偏差，不是只看左右孩子的大小比较，是和左右子树最小最大值比较，嗯嗯，搞错了，所以需要多记录一下子树最小最大值

题解代码写得很简洁，nice

class Solution {
public:
    static constexpr int inf = 0x3f3f3f3f;
    int res;
    struct SubTree {
        bool isBST;
        int minValue;
        int maxValue;
        int sumValue;
        SubTree(bool isBST, int minValue, int maxValue, int sumValue) : isBST(isBST), minValue(minValue), maxValue(maxValue), sumValue(sumValue) {}
    };

    SubTree dfs(TreeNode* root) {
        if (root == nullptr) {
            return SubTree(true, inf, -inf, 0);
        }
        auto left = dfs(root->left);
        auto right = dfs(root->right);

        if (left.isBST && right.isBST &&
                root->val > left.maxValue && 
                root->val < right.minValue) {
            int sum = root->val + left.sumValue + right.sumValue;
            res = max(res, sum);
            return SubTree(true, min(left.minValue, root->val), 
                           max(root->val, right.maxValue), sum);
        } else {
            return SubTree(false, 0, 0, 0);
        }
    }

    int maxSumBST(TreeNode* root) {
        res = 0;
        dfs(root);
        return res;
    }
};

Review

【TED演讲】拖延症人的内心世界

拖延症的原因:
人类是动物进化来的，动物只需要吃饱睡好，繁殖，所以人类在现代社会里，这些都很容易满足的时候，做其他更多有意义的事情的动力就会降低为0。

就相当于我们的脑海里有一个理智的人，然后有一个贪图及时享受的猴子

一般情况下，及时享乐的猴子都会占据上风，让人变得拖延
当然在应对一些有deadline截止日期的任务，我们可能会在deadline快到的时候突然爆发一个恐惧怪兽。
恐惧怪兽把猴子吓跑，然后理智的人开始干活，这对有deadline的任务很有效
但是有些任务是没有deadline的，比如健身，陪伴家人，改善亲密关系，等等，这样我们就无法召唤我们的恐惧怪兽，所以我们需要思考我们的大限将至，把每天当做人生最后两年来活，给许多事情都设置一个deadline，这样我们就会好好去做了–不过当然也包括享受生活

Tips

理解 LSM Tree：一种高效读写的存储引擎

感谢耗子叔，永远怀念耗子叔

Algorithm

Review

Tips

Share