LEETCODE 1373. Maximum Sum BST in Binary Tree 解题思路分析

题目大意:

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

给你一棵以 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

提示:

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1373

这是一道二叉搜索树(BST)的题目,我们需要采用递归方式来解题。解题时,我们判断每一个节点下面的子树是否是一颗合理的BST,如果是的话,我们还需要计算这颗子树所有节点的和。另外判断当前点是合理BST的条件很苛刻,必须同时满足以下要求:

  1. 当前点的值大于其左子树中的最大值。
  2. 当前点的值小于其右子树中的最小值。
  3. 左子树是BST。
  4. 右子树是BST。

通过上面的分析发现,我们在使用递归函数时,需要将大量信息返回给上层递归函数:

  1. 当前节点下方是否是BST
  2. 当前节点下方所有节点和
  3. 当前节点下方最大值
  4. 当前节点下方最小值

因此,我们需要建立一个Result类,来保存上述变量,同时Result也是递归函数的返回值。

递归函数中,对于任意一节点,我们首先递归求出其左子节点的返回值leftResult,以及右子节点的返回值rightResult(子节点为空时,上述返回值也为空)。这时我们可以列举出当前节点下子树为合理BST的几种情况:

  1. 当leftResult为空,并且rightResult为空时,当前节点为叶子节点,叶子节点本身属于合理BST,当前子树中最大值为当前节点值,最小值也是当前节点值,同时子树所有节点和也是当前节点值。
  2. 当leftResult为空,并且rightResult不空时,也就是当前节点下只存在右子树的情况,此时,如果右子树是BST,并且当前节点小于右子树中最小值,那么当前节点下子树是合理BST,当前子树中最大值为右子树中最大值,最小值是当前节点值,当前子树所有节点和是当前节点值加上右子树节点和。
  3. 当rightResult为空,并且leftResult不空时,也就是当前节点下只存在左子树的情况,此时,如果左子树是BST,并且当前节点大于左子树中最大值,那么当前节点下子树是合理BST,当前子树中最大值为当前节点,最小值是左子树中最小值,当前子树所有节点和是当前节点值加上左子树节点和。
  4. 当rightResult和leftResult均不空时,如果左子树是BST并且右子树也是BST,并且当前节点值大于左子树最大值,并且当前节点值小于右子树最小值,那么当前节点下是合理BST,当前子树中最大值是右子树最大值,最小值是左子树最小值,节点和是当前节点值加上左子树节点和再加上右子树节点和。

以上即是当前节点为合理BST的四种情况,在当前节点下子树是合理BST时,我们需要使用当前的子树节点和去更新全局最大值。除了上述情况之外,当前节点下都不能组成合理的BST,此时,子树的最大值,最小值以及节点和都可以重置为当前节点值(重置为任何值都无所谓,对于非法BST中的数值我们不会再使用到)。

实现代码:

class Result{ // 递归函数返回结果
    int sum; // 当前节点下子树所有节点和
    int min, max; // 当前子树下最小值和最大值
    boolean isBST; // 当前子树是否是合理BST
    public Result(int s, boolean isBST, int min, int max) {
        sum = s;
        this.min = min;
        this.max = max;
        this.isBST = isBST;
    }
}
int res=0; // 返回结果
public int maxSumBST(TreeNode root) {
    help(root); // 递归求解
    return res;
}

Result help(TreeNode root){
    // 左子节点以及右子节点返回结果
    Result leftResult=null,rightResult=null;
    // 左子节点不为空
    if(root.left!=null){
        // 递归求解左子节点返回结果
        leftResult=help(root.left);
    }
    // 右子节点不为空
    if(root.right!=null){
        // 递归求解右子节点返回结果
        rightResult=help(root.right);
    }
    // 当前节点是叶子节点
    if(leftResult==null&&rightResult==null){
        // 更新全局最大值
        res=Math.max(res,root.val);
        // 返回当前节点下子树信息:合理BST
        return new Result(root.val,true,root.val,root.val);
    }
    // 当前节点下左右子节点都不为空
    if(leftResult!=null&&rightResult!=null){
        // 左右子树都是BST,并且当前节点小于右子树最小值并且大于左子树最大值
        if(rightResult.isBST&&leftResult.isBST&&
           root.val<rightResult.min&&root.val>leftResult.max){
            // 当前节点下节点和
            int sum=leftResult.sum+rightResult.sum+root.val;
            // 更新全局最大值
            res=Math.max(res,sum);
            // 返回当前节点下子树信息:合理BST
            return new Result(sum,true,leftResult.min,rightResult.max);
        }
    }
    // 当前节点下左子节点为空,右子树是BST,并且当前节点小于右子树最小值
    if(leftResult==null&&rightResult.isBST&&root.val<rightResult.min){
        // 当前节点下节点和
        int sum=rightResult.sum+root.val;
        // 更新全局最大值
        res=Math.max(res,sum);
        // 返回当前节点下子树信息:合理BST
        return new Result(sum,true,root.val,rightResult.max);
    }
    // 当前节点下右子节点为空,左子树是BST,并且当前节点大于左子树最大值
    if(rightResult==null&&leftResult.isBST&&root.val>leftResult.max){
        int sum=leftResult.sum+root.val;
        res=Math.max(res,sum);
        return new Result(sum,true,leftResult.min,root.val);
    }
    // 除了上述情况之外,当前节点下一定是非法BST
    return new Result(root.val,false,root.val,root.val);
}

本题解法执行时间为5ms。

Runtime: 5 ms, faster than 91.91% of Java online submissions for Maximum Sum BST in Binary Tree.

Memory Usage: 58.1 MB, less than 100.00% of Java online submissions for Maximum Sum BST in Binary Tree.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1373-maximum-sum-bst-in-binary-tree-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。