题目描述

给你一棵以 root 为根的 二叉树，请你返回 任意 二叉搜索子树的最大键值和。

二叉搜索树的定义如下：

• 任意节点的左子树中的键值都 小于 此节点的键值。
• 任意节点的右子树中的键值都 大于 此节点的键值。
• 任意节点的左子树和右子树都是二叉搜索树。

样例

输入：root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
输出：20
解释：键值为 3 的子树是和最大的二叉搜索树。

输入：root = [4,3,null,1,2]
输出：2
解释：键值为 2 的单节点子树是和最大的二叉搜索树。

输入：root = [-4,-2,-5]
输出：0
解释：所有节点键值都为负数，和最大的二叉搜索树为空。

输入：root = [2,1,3]
输出：6

输入：root = [5,4,8,3,null,6,3]
输出：7

限制

• 每棵树有 1 到 40000 个节点。
  每个节点的键值在 [-4 * 10^4 , 4 * 10^4] 之间。

算法

(递归) $O(n)$

1. 定义递归函数：参数为当前结点，返回值为三元组，以当前结点为根结点的二叉搜索树的总和，子树中的最小值和最大值。
2. 分别递归左右儿子结点，得到返回值。如果不存在，则定义返回值为默认值（见代码）。
3. 判断左右子树和当前结点是否构成二叉搜索树，即当前结点的值是否大于左子树最大值，以及小于右子树最小值。
4. 如果可以，则更新答案，然后返回新的三元组。否则，返回一个表示非法的二叉搜索树的三元组（见代码）。

时间复杂度

• 每个结点遍历一次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(h)$ 的系统栈空间，其中 $h$ 为树的最大高度。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    struct T {
        int sum, lo, hi;
        T(int sum_, int lo_, int hi_):sum(sum_), lo(lo_), hi(hi_){}
    };

    int ans;

    T solve(TreeNode *rt) {
        T tl(0, rt->val, INT_MIN);
        T tr(0, INT_MAX, rt->val);

        if (rt->left) tl = solve(rt->left);
        if (rt->right) tr = solve(rt->right);

        if (tl.hi < rt->val && rt->val < tr.lo) {
            ans = max(ans, tl.sum + rt->val + tr.sum);
            return T(tl.sum + rt->val + tr.sum, tl.lo, tr.hi);
        }

        return T(INT_MIN, INT_MIN, INT_MAX);
    }

    int maxSumBST(TreeNode* root) {
        ans = 0;
        solve(root);
        return ans;
    }
};