国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[LeetCode] 333. Largest BST Subtree

tigerZH / 2292人閱讀

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 descendants.

Example:

Input: [10,5,15,1,8,null,7]

   10 
   /  
  5  15 
 /     
1   8   7

Output: 3
Explanation: The Largest BST Subtree in this case is the highlighted one.
             The return value is the subtree"s size, which is 3.

Follow up:
Can you figure out ways to solve it with O(n) time complexity?

Solution

First try:

class Solution {
    public int largestBSTSubtree(TreeNode root) {
        if (root == null) return 0;
        if (isBST(root)) return largestBSTSubtree(root.left)+largestBSTSubtree(root.right)+1;
        return Math.max(largestBSTSubtree(root.left), largestBSTSubtree(root.right));
    }
    private boolean isBST(TreeNode root) {
        if (root == null) return true;
        if (root.left != null && findMax(root.left) >= root.val) return false;
        if (root.right != null && findMin(root.right) <= root.val) return false;
        if (isBST(root.left) && isBST(root.right)) return true;
        return false;
    }
    private int findMax(TreeNode root) {
        while (root.right != null) root = root.right;
        return root.val;
    }
    private int findMin(TreeNode root) {
        while (root.left != null) root = root.left;
        return root.val;
    }
}

Optimized:

class Solution {
    public int largestBSTSubtree(TreeNode root) {
        if (root == null) return 0;
        if (isBST(root, null, null)) return largestBSTSubtree(root.left)+largestBSTSubtree(root.right)+1;
        return Math.max(largestBSTSubtree(root.left), largestBSTSubtree(root.right));
    }
    private boolean isBST(TreeNode root, Integer min, Integer max) {
        if (root == null) return true;
        if (min != null && min >= root.val) return false;
        if (max != null && max <= root.val) return false;
        if (isBST(root.left, min, root.val) && isBST(root.right, root.val, max)) return true;
        return false;
    }
}

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/72038.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 評論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 評論0 收藏0
  • 333. Largest BST Subtree

    10 / 5 15 / 1 8 7 return 3 public class Solution { public int largestBSTSubtree(TreeNode root) { if(root == null) return 0; int[] res = recursive(root); ...

    DataPipeline 評論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 評論0 收藏0
  • [LeetCode] 501. Find Mode in Binary Search Tree

    Problem Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST. Assume a BST is defined as follows: The left subtree of a node c...

    NikoManiac 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<