成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[LeetCode] Largest BST Subtree

Youngdze / 945人閱讀

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 of its descendants.
Here"s an example:

    10
    / 
   5  15
  /     
 1   8   7

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

Hint:

You can recursively use algorithm similar to 98. Validate Binary Search Tree at each node of the tree, which will result in O(nlogn) time complexity.

Follow up:

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

Solution 
public class Solution {
    public int largestBSTSubtree(TreeNode root) {
        if (root == null) return 0;
        if (isValidBST(root)) return largestBSTSubtree(root.left)+largestBSTSubtree(root.right)+1;
        else return Math.max(largestBSTSubtree(root.left), largestBSTSubtree(root.right));
    }
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    public boolean dfs(TreeNode root, long min, long max) {
        if (root == null) return true;
        if (root.val <= min || root.val >= max) return false;
        return dfs(root.left, min, root.val) && dfs(root.right, root.val, max);
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65189.html

相關(guān)文章

  • LeetCode[333] Largest BST Subtree

    摘要：復(fù)雜度思路考慮對于每一個節(jié)點(diǎn)來說，能組成的的。那么并且所以我們需要兩個返回值，一個是這個是不是，另一個是當(dāng)前的能組成的最大的值。代碼這個能構(gòu)成一個這個不能構(gòu)成一個 LeetCode[333] Largest BST Subtree Given a binary tree, find the largest subtree which is a Binary SearchTree (B...

    WrBug 評論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 評論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

發(fā)表評論

0條評論

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