1373. 二叉搜索子树的最大键值和
利用好后序遍历
暴力做法就是: 遍历每一个节点,分别判断以该节点为根的子树是否是BST,是的话,计算出来该二叉搜索树的键值和,更新最大值。最后返回结果。
我们知道二叉搜索树的定义如下:
- 任意节点的左子树中的键值都 小于 此节点的键值。
- 任意节点的右子树中的键值都 大于 此节点的键值。
- 任意节点的左子树和右子树都是二叉搜索树。
所以判读的步骤如下:
1. 先判断其左右两颗子树是否是BST
2. 是否满足 左子树中的最大键值< 根节点的值< 右子树的最小键值。
这样的话,根节点的结果需要用到其左右子树的结果,那我们可以采用后序遍历的基本框架。
返回值的话,我们要考虑到 上面的判断条件,以及最后还需要计算最大键值和。综上,后序遍历的返回值为一个数组 res.
res[0] =1 表示以该节点为根的子树是BST =0 则不是
res[1] 记录的是以该节点为根的子树的最大值
res[2] 记录的是以该节点为根的子树的最小值
res[3] 记录的是以该节点为根的子树的键值和
参考的是labuladong 的刷二叉树
Java代码
class Solution {
int maxSum=0 ;
public int maxSumBST(TreeNode root) {
traverse(root);
return maxSum;
}
/**
int[] 4
[0] 表示以root 为根的树 是否是二叉搜索树,1 表示是,0 表示否
[1] 表示以root 为根的树 的节点的值的最大值
[2] 表示以root 为根的树 的节点的值的最小值
[3] 表示以root 为根的树 的节点的值的和
*/
private int[] traverse(TreeNode root){
if(root==null){
return new int[]{1,Integer.MIN_VALUE,Integer.MAX_VALUE,0};
}
int[]left=traverse(root.left);
int []right=traverse(root.right);
int[]res=new int[4];
if(left[0]==1&&right[0]==1){
if(left[1]<root.val&&right[2]>root.val){
res[0]=1;
}else{
res[0]=0;
}
}else{
res[0]=0;
}
res[1]=Math.max(root.val,right[1]);
res[2]=Math.min(root.val,left[2]);
res[3]=root.val+left[3]+right[3];
if(res[0]==1){
maxSum=Math.max(maxSum,res[3]);
}
return res;
}
}