[LeetCode 1373]二叉搜索子树的最大键值和

题目描述

链接：[LeetCode 1373]二叉搜索子树的最大键值和

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

二叉搜索树的定义如下：

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

示例 1

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

示例2

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

示例 3

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

示例4

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

示例5

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

提示

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

思路分析：

1.树的题一般考察的都是递归，那么dfs应该返回什么值？
要判断一棵树是二叉搜索树，则需要满足：

• 根节点的左子树是二叉搜索树，且左子树最大值比根节点要小
• 根节点的右子树是二叉搜索树，且右子树最小值比根节点要大

此外要求树的键值和，还需要求左子树和右子树的键值和

所以返回值为（键值和，最小值，最大值）这样一个三元组(s, min, max)

2.特殊情况的处理：
(1).如果左子树为空，那么要左子树三元组应该赋值为多少？

如图：

首先，左子树为空，那么显而易见，s1 = 0;

其次，对于根节点的返回值，如果左子树为空，那么min0 = root->val，又由图中的等式可知，min1 = min0 = root->val;

最后，左子树为空时，max1本身是不参与传递的，但是以root为根节点的二叉树是否是二叉搜索树需要满足root->val > max1的，所以max1的值必须小于root->val，这里保证恒成立就行，所以可以设置为-INF，其中INF为上限

(2).如果右子树为空，那么要右子树三元组应该赋值为多少？

同理，右子树为空，s2=0；

其次，对于根节点的返回值，如果右子树为空，那么max0 = root->val，又由图中的等式可知，max2 = max0 = root->val;

最后，右子树为空时，以root为根节点的二叉树是否是二叉搜索树需要满足root->val < min2的, 所以min2的值必须小于root->val，这里保证恒成立就行，所以可以设置为INF，其中INF为上限

代码

代码来源：acwing

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    const int INF = 1e8;
    int res = 0;
    
    vector<int> dfs(TreeNode* root)
    {
        vector<int> left{0, root->val, -INF};
        vector<int> right{0, INF, root->val};

        if(root->left) left = dfs(root->left);
        if(root->right) right = dfs(root->right);

        if(left[2] < root->val && root->val < right[1])
        {
            int s = left[0] + right[0] + root->val;
            res = max(res, s);
            return {s, left[1], right[2]};
        }

        return {-INF, -INF, INF};
    }
    int maxSumBST(TreeNode* root) {
        dfs(root);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38