您的浏览器不支持CSS3,建议使用Firfox、Chrome等浏览器,以取得最佳显示效果

LeetCode:最大二叉搜索子树

开发技术 639℃ 0 7个月前 (04-04)

摘要

LeetCode:最大二叉搜索子树

题目

333. Largest BST Subtree

给定一个二叉树,找到其中最大的二叉搜索树(BST)子树,其中最大指的是子树节点数最多的。注意:子树必须包含其所有后代。

解答

一次遍历,visit方法返回从该节点以下找到的BST信息,包括根节点、最大值、最小值、尺寸。为了方便返回多个值,也方便代码阅读,封装成了一个Result类。

有几种可能:

  • 左右子树均为BST,且满足 左子树max < node < 右子树min,则当前树也是BST
  • 左右子树中都搜索到了BST,则返回size更大的
  • 左右子树之一搜索到了BST,则直接返回
  • 左右子树都没搜索到BST,则返回null

代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    class Result {
        TreeNode node; // BST根节点
        int size; // BST的size
        int max; // BST的最大值
        int min; // BST的最小值
    }

    public int largestBSTSubtree(TreeNode root) {
        Result r = visit(root);
        return r == null ? 0 : r.size;
    }

    public Result visit(TreeNode node) {
        if (node == null) return null;

        Result l = null, r = null;
        if (node.left != null) l = visit(node.left);
        if (node.right != null) r = visit(node.right);

        // 当前树为BST
        boolean lValid = (l == null || (l.node == node.left && l.max < node.val));
        boolean rValid = (r == null || (r.node == node.right && r.min > node.val));
        if (lValid && rValid) {
            Result result = new Result();
            result.node = node;
            result.max = r == null ? node.val : r.max;
            result.min = l == null ? node.val : l.min;
            result.size = (l == null ? 0 : l.size) + (r == null ? 0 : r.size) + 1;
            return result;
        }

        // 左右子树中找到了BST
        if (l != null && r != null) {
            return l.size > r.size ? l : r;
        }
        if (l != null) return l;
        if (r != null) return r;

        return null;
    }
}

最后,欢迎扫码关注微信公众号。微软 / Shopee / Coupang / BAT等国内外企业内推、行业和技术交流,也可以加我微信 jzj2015(注明来自博客),拉你进技术群。

本文由原创,转载请注明来源:https://www.paincker.com/largest-bst-subtree
(标注了原文链接的文章除外)

0

暂无评论

评论前:需填写以下信息,或 登录

用户登录

忘记密码?