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

資訊專欄INFORMATION COLUMN

LeetCode[333] Largest BST Subtree

WrBug / 1425人閱讀

摘要：復(fù)雜度思路考慮對于每一個節(jié)點來說，能組成的的。那么并且所以我們需要兩個返回值，一個是這個是不是，另一個是當(dāng)前的能組成的最大的值。代碼這個能構(gòu)成一個這個不能構(gòu)成一個

LeetCode[333] 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.
Recursion

復(fù)雜度
O(N), O(lgN)

思路
考慮對于每一個節(jié)點來說，能組成的largest binary tree的size。

if(isBinary(node.left) && isBinary(node.right)) {
    if(node.val > node.left.val && node.val < node.right.val) {
        //
        那么node is binary
        并且node.cnt = node.left.cnt + node.right.cnt;
    }
}
else {
    return node is not binary && Math.max(node.left.cnt, node.right.cnt);
}

所以我們需要兩個返回值，一個是這個node是不是binary tree，另一個是當(dāng)前的node能組成的最大size的值。

可以考慮定義一個新node來返回這兩個結(jié)果，或者通過返回一個數(shù)組，數(shù)組里面包含著兩個值來返回這兩個結(jié)果。

代碼

int num = 0;
public int largestBSTSubtree(TreeNode root) {
    helper(root);
    return num;
}

// in[] = {isBST, size, max, min};
public int[] helper(TreeNode root) {
    if(root == null) return new int[]{1, 0, Integer.MIN_VALUE, Integer.MAX_VALUE};
    int[] left = helper(root.left);
    int[] right = helper(root.right);
    int res = new int[4];
    res[2] = Math.max(root.val, right[2]);
    res[3] = Math.min(root.val, left[3]);
    // 這個node能構(gòu)成一個Binary tree
    if(left[0] == 1 && right[0] == 1 && root.val > left[2] && root.val < right[3]) {
        res[0] = 1;
        res[1] = left[1] + right[1] + 1;
        num = Math.max(num, res[1]);
        return res;
    }
    // 這個node不能構(gòu)成一個binary tree
    res[0] = 0;
    res[1] = Math.max(left[1], right[1]);
    return res;
}

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

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

相關(guān)文章

  • [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

  • [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

發(fā)表評論

0條評論

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