题解 | 二叉搜索子树的最大键值和

题干分析

题设给定我们一个二叉树，要求我们寻找其中的二叉搜索子树，并返回其中所有节点的节点总和的最大值。

算法思路

我们判断一颗树是否为二叉搜索树定义上是左子树节点严格小于根节点值，右子树节点严格大于根节点。

其实如果一颗二叉搜索树所有节点同时也满足左子树最大节点值小于根节点，右子树最小节点值大于根节点（前提是有左右子树）也可以判断其为二叉搜索树。依据此，我们后序遍历题设给予我们的树，找到左右子树的最小，最大与节点值总和。然后进行判断。

同时我们注意到，我们要求所有节点均需要满足条件才能成为二叉搜索树，因此只要出现不符合条件的子树，我们需要让这颗子树的返回值永远导致其父节点所属子树不为二叉搜索树，因此我们不妨将最小节点值设为最小（INT_MIN），最大节点值设为最大（INT_MAX），以此破坏二叉搜索性质。

实现代码

class Solution {
    int ans = 0;
    vector<int> dfs(TreeNode *cur) {
        // min, max, sum
        vector ret = {INT_MAX, INT_MIN, 0};
        if (cur) {
            auto left = dfs(cur->left);
            auto right = dfs(cur->right);
            // 是二叉搜索树
            if (left[1] < cur->val && right[0] > cur->val) {
                ret[0] = min(left[0], cur->val);
                ret[1] = max(right[1], cur->val);
                ret[2] = left[2] + right[2] + cur->val;
                ans = max(ans, ret[2]);
            } else ret = {INT_MIN, INT_MAX, 0};
        }
        return ret;
    }
public:
    int maxSumBST(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

复杂度分析

• 时间复杂度：最坏情况下每个节点访问一次，时间复杂度为
• 空间复杂度：最坏情况下二叉树退化为一条链，递归空间消耗为