leetcode.5339. 二叉搜索子树的最大键值和

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

二叉搜索树判定

class Solution {
public:
    struct node{int v[4];};
    int ans=0;
    node dfs(TreeNode* &root){
        TreeNode* L=root->left;
        TreeNode* R=root->right;
        if(L==NULL||R==NULL){
            if(L&&!R){
                node V=dfs(L);
                if(root->val>V.v[0]&&V.v[3]){
                    ans=max(ans,V.v[2]);
                    ans=max(ans,V.v[2]+root->val);
                    return {max(V.v[0],root->val),min(V.v[1],root->val),V.v[2]+root->val,1};
                }
                return {max(V.v[0],root->val),min(V.v[1],root->val),V.v[2]+root->val,0};
            }else if(!L&&R){
                node V=dfs(R);
                if(root->val<V.v[1]&&V.v[3]){
                    ans=max(ans,V.v[2]);
                    ans=max(ans,V.v[2]+root->val);
                    return {max(V.v[0],root->val),min(V.v[1],root->val),V.v[2]+root->val,1};
                }
                return {max(V.v[0],root->val),min(V.v[1],root->val),V.v[2]+root->val,0};
            }else{
                ans=max(ans,root->val);
                return {root->val,root->val,root->val,1};
            }
        }
        node Lsum=dfs(L);
        node Rsum=dfs(R);
        if(root->val>Lsum.v[0]&&root->val<Rsum.v[1]&&Lsum.v[3]&&Rsum.v[3]){
            ans=max(ans,Lsum.v[2]+Rsum.v[2]+root->val);
            return {max(max(Lsum.v[0],Rsum.v[0]),root->val),min(min(Lsum.v[1],Rsum.v[1]),root->val),Lsum.v[2]+Rsum.v[2]+root->val,1};

        }
        return {max(max(Lsum.v[0],Rsum.v[0]),root->val),min(min(Lsum.v[1],Rsum.v[1]),root->val),Lsum.v[2]+Rsum.v[2]+root->val,0};
    }
    int maxSumBST(TreeNode* root) {
        if(root==NULL)return 0;
        dfs(root);
        return ans;
    }
};