秋招每日一题T31——二叉搜索子树的最大键值和

题目描述

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

二叉搜索树的定义如下：

• 任意节点的左子树中的键值都 小于 此节点的键值。
• 任意节点的右子树中的键值都 大于 此节点的键值。
• 任意节点的左子树和右子树都是二叉搜索树。
  
  来源：力扣（LeetCode）
  链接：https://leetcode.cn/problems/maximum-sum-bst-in-binary-tree
  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

①这棵树可能不是一棵二叉搜索树，因此要在树中寻找满足二叉搜索树条件的子树（以当前结点为子树的根节点，左子树的最大值小于当前节点键值，右子树的最小值大于当前节点的键值），求这棵子树的键值和。
②对根节点进行递归，寻找满足条件的键值和。定义一个存储三元组的结构体，这个三元组代表一棵子树，存储该子树的键值和、左子树的最大值（需要小于当前根节点键值，用于判断是否满足二叉搜索树条件）和右子树的最小值（同上）。
③当前子树是二叉搜索树的条件是：以当前结点为子树的根节点，左子树的最大值小于当前节点键值，右子树的最小值大于当前节点的键值。 如果不满足这个条件，就返回一个非法的三元组：左子树的最大值为INT_MAX，右子树的最小值为INT_MIN，树和为INT_MIN。 （这样使得左子树的最大值大于当前节点键值，右子树的最小值小于当前节点键值，一定是一棵非法的二叉搜索树）
④如果满足③的条件，就更新答案ans，即，令ans等于当前节点键值＋左子树之和＋右子树之和，并返回一棵以当前结点构造的二叉搜索树三元组。（右子树的最大值，左子树的最小值，子树和）

代码

/**
 * 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:
    int ans;
    struct node{
        int hi,lo,sum;
        node(int hi_, int lo_, int sum_):hi(hi_), lo(lo_), sum(sum_){}
    };
    int maxSumBST(TreeNode* root) {
        ans = 0;
        solve(root);
        return ans;
    }
    node solve(TreeNode* rt){
        node tl = node(INT_MIN,rt->val,0);
        node tr = node(rt->val,INT_MAX,0);
        if(rt->left)    tl = solve(rt->left);
        if(rt->right)   tr = solve(rt->right);
        if(tl.hi < rt->val && tr.lo > rt->val){
            ans = max(ans,rt->val+tl.sum+tr.sum);
            return node(tr.hi,tl.lo,rt->val + tl.sum + tr.sum);
        }
        return node(INT_MAX,INT_MIN,INT_MIN);
    }
};
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