leetcode.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;
}
};