333. Largest BST Subtree

DataPipeline 发布于2019-08-16 10:35 / 1793人阅读

public class Solution {
    public int largestBSTSubtree(TreeNode root) {
        if(root == null) return 0;
        int[] res = recursive(root);
        return res[2];
    }
    
    public int[] recursive(TreeNode root){
        int[] res = new int[5];
        // res[0] BST or Not?
        // res[1] total number nodes of subtree
        // res[2] max number of BST subtree 
        // res[3] min
        // res[4] max
        res[0] = 1; res[3] = Integer.MAX_VALUE; res[4] = Integer.MIN_VALUE;
        if(root == null) return res;
        
        int[] resL = recursive(root.left);
        int[] resR = recursive(root.right);
        if(resL[0] == 0 || resR[0] == 0 || resL[4] >= root.val || resR[3] <= root.val) 
            res[0] = 0;
        res[1] = resL[1] + resR[1] + 1;
        res[2] = (res[0] == 1) ? res[1]: Math.max(resL[2], resR[2]);
        res[3] = root.val < resL[3] ? root.val : resL[3];
        res[4] = root.val > resR[4] ? root.val : resR[4];
        return res;
    }
}

私有云 GPU服务器 Largest Subtree BST git-subtree

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/70080.html

LeetCode[333] Largest BST Subtree

摘要：复杂度思路考虑对于每一个节点来说，能组成的的。那么并且所以我们需要两个返回值，一个是这个是不是，另一个是当前的能组成的最大的值。代码这个能构成一个这个不能构成一个 LeetCode[333] Largest BST Subtree Given a binary tree, find the largest subtree which is a Binary SearchTree (B...

WrBug 2019-08-14 15:03 评论0 收藏0
[LeetCode] 333. Largest BST Subtree

Problem Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it. Note:A subtree must include all of its descen...

tigerZH 2019-08-16 13:37 评论0 收藏0
[LeetCode] Largest BST Subtree

Largest BST Subtree Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it. Note: A subtree must include all ...

Youngdze 2019-08-14 14:55 评论0 收藏0
[LeetCode] 776. Split BST

Problem Given a Binary Search Tree (BST) with root node root, and a target value V, split the tree into two subtrees where one subtree has nodes that are all smaller or equal to the target value, whil...

baiy 2019-08-16 13:45 评论0 收藏0
二叉排序树

摘要：节点的构造函数默认为其初始化都是。二叉排序树插入插入节点只要遵循一个原则就好大与就向中插入，小于就向插入。初始化数据树现在来试试实例化一个来看看效果。 JavaScript 数据结构篇之 BST 前言有段时间没有写文章了，整个人感觉变得有点懒散了，大家可不要向我一样哦~今天开始 seaconch 打算开始记录 JavaScript 数据结构的学习经历。至此，开始。课本：《学习J...

Soarkey 2019-08-23 14:14 评论0 收藏0