Created
March 14, 2018 03:26
-
-
Save jianminchen/53236a7f96390cf27e3b39b0ec2e0d30 to your computer and use it in GitHub Desktop.
Leetcode 333 - biggest binary search tree - peer performed very well
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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? | |
class Node{ | |
boolean isBST; | |
int size; | |
int min, max; | |
public Node(){ | |
isBST=true | |
size=0; | |
} | |
} | |
10 | |
/ \ | |
5 15 | |
/ \ \ | |
1 8 7 | |
n n | |
1 -> Node() min=INteger.MIN_VALUE, max=1, size 1 | |
8 -> min=Integer.MIN_VALUE, max=1, size 1 | |
//https://github.com/mission-peace/interview/blob/master/src/com/interview/tree/LargestBSTInBinaryTree.java | |
/** | |
* Definition for a binary tree node. | |
* public class TreeNode { | |
* int val; | |
* TreeNode left; | |
* TreeNode right; | |
* TreeNode(int x) { val = x; } | |
* } | |
*/ | |
class Solution { | |
// https://www.youtube.com/watch?v=4fiDs7CCxkc | |
class Node{ | |
int min, max, size; | |
boolean isBST; | |
public Node(){ | |
min=Integer.MAX_VALUE; | |
max=Integer.MIN_VALUE; | |
isBST=true; | |
size=0; | |
} | |
} | |
public int largestBSTSubtree(TreeNode root) { | |
Node r=get(root); | |
return r.size; | |
} | |
//bc | |
if root is null | |
return new Node(); | |
Node left=get(root.left) | |
if(leftisbst or rightisbst) | |
root val | |
< < | |
left val max right val min | |
left size + right size +1 | |
else | |
math left size, right size | |
https://www.youtube.com/watch?v=4fiDs7CCxkc | |
public Node get(TreeNode root) { | |
//bc | |
if(root==null){ | |
return new Node(); | |
} | |
//post order because left, right, then root | |
Node left = get(root.left); | |
Node right = get(root.right); | |
Node cur = new Node(); | |
//if either child is not a BST or | |
//if the left child's max is larger than root or | |
//if the right child's min is smaller than the root | |
//it's NOT a BST | |
if(!left.isBST || | |
!right.isBST || | |
left.max >= root.val || right.min <= root.val){ | |
cur.isBST=false; | |
//get max of right and left size | |
cur.size = Math.max(left.size, right.size); // ? | |
return cur; | |
} | |
//if it makes it here, then it is a BST | |
cur.isBST = true; | |
//size is both children plus this node | |
cur.size = left.size + right.size + 1; | |
//if the left child is null, set min to root.val, | |
//otherwise set it to child's min | |
cur.min = root.left != null? left.min : root.val; | |
//if the right child is null, set min to root.val, | |
//otherwise set it to child's min | |
cur.max = root.right!= null? right.max : root.val; | |
return cur; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment