BiruLyu
6/3/2017 - 5:32 PM

## 333. Largest BST Subtree(#1).java

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def largestBSTSubtree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def dfs(root) :
if not root :
return 0, 0, float('inf'), float('-inf')
N1, n1, min1, max1 = dfs(root.left)
N2, n2, min2, max2 = dfs(root.right)
n = n1 + n2 + 1 if max1 < root.val < min2 else float('-inf')
return max(N1, N2, n), n, min(min1, root.val), max(max2, root.val)
return dfs(root)[0]``````
``````/*
1. root.val > root.left.rightmost.val
2. root.val < root.right.leftmost.val
3. if the subTree is a BST, return the current num of the nodes
4. Can use int[] instead of defining a nested class Node
*/

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private class Node{
int min;
int max;
int count;
boolean flag;

public Node(int min, int max, int count, boolean flag) {
this.min = min;
this.max = max;
this.count = count;
this.flag = flag;
}
}
public int largestBSTSubtree(TreeNode root) {
int[] count =  {0};
isBST(root, count);
return count[0];
}

public Node isBST(TreeNode root, int[] count) {
if(root == null) return new Node(-1, -1, 0, true);
if(root.left == null && root.right == null) {
count[0] = Math.max(count[0], 1);
return new Node(root.val, root.val, 1, true);
}
Node left = isBST(root.left, count);
Node right = isBST(root.right, count);

if(!left.flag || !right.flag) {
return new Node (-1, -1, 0, false);
}
if(root.left == null && root.val < right.min) {
Node temp = new Node(root.val, right.max, right.count + 1, true);
count[0] = Math.max(count[0], temp.count);
return temp;
} else if (root.right == null && root.val > left.max) {
Node temp = new Node(left.min, root.val, left.count + 1, true);
count[0] = Math.max(count[0], temp.count);
return temp;
} else if(root.val < right.min && root.val > left.max) {
Node temp = new Node(left.min, right.max, left.count + right.count + 1, true);
count[0] = Math.max(count[0], temp.count);
return temp;
}

return new Node(-1, -1, 0, false);
}
}

/*
[10,5,15,1,8,null,7]
[10,3,7,2,null,8,9,1,null,10,11]
[4,3,7,2,null,8,9,1,null,10,11]
[4,3,8,2,null,6,9,1,null,5,7]
[3,1,null,4,null,2,null,5]
[3,2,4,null,null,1]
*/``````
``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
class Node {
int size;
int lower, upper;
public Node (int size, int lower, int upper) {
this.size = size;
this.lower = lower;
this.upper = upper;
}
}
public int largestBSTSubtree(TreeNode root) {
if (root == null) return 0;
int[] count = new int[1];
helper(root, count);
return count[0];
}

public Node helper(TreeNode cur, int[] count) {
if (cur == null) return new Node(0, Integer.MAX_VALUE, Integer.MIN_VALUE);
Node left = helper(cur.left, count);
Node right = helper(cur.right, count);
if (left.size < 0 || right.size < 0 || left.upper >= cur.val || right.lower <= cur.val) {
return new Node (-1, 0, 0);
}

int size = left.size + right.size + 1;
count[0] = Math.max(count[0], size);
return new Node(size, Math.min(left.lower, cur.val), Math.max(right.upper, cur.val));
}
}``````