資訊專(zhuān)欄INFORMATION COLUMN
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.
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?
Solutionpublic 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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/65189.html
摘要：復(fù)雜度思路考慮對(duì)于每一個(gè)節(jié)點(diǎn)來(lái)說(shuō)，能組成的的。那么并且所以我們需要兩個(gè)返回值，一個(gè)是這個(gè)是不是，另一個(gè)是當(dāng)前的能組成的最大的值。代碼這個(gè)能構(gòu)成一個(gè)這個(gè)不能構(gòu)成一個(gè) LeetCode[333] Largest BST Subtree Given a binary tree, find the largest subtree which is a Binary SearchTree (B...
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...
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); ...
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...
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...
閱讀 1822·2021-11-24 10:18
閱讀 2354·2021-11-18 13:20
閱讀 2420·2021-08-23 09:46
閱讀 1129·2019-08-30 15:56
閱讀 2921·2019-08-30 15:53
閱讀 891·2019-08-30 14:22
閱讀 564·2019-08-29 15:34
閱讀 2633·2019-08-29 12:14
