Leetcode/F家 -- 98.Validate Binary Search Tree + 333. Largest BST Subtree

98.Validate Binary Search Tree(recur)

• Medium

查是否BST,要保证左边的node值小于右边值
https://leetcode.com/problems/validate-binary-search-tree/

company: Amazon Microsoft Bloomberg Facebook

思路： - use recursion, traverse the tree, with current, low, high nodes
            - bst: min node < max, fill the min & max accordingly
            - eg:    14 call(root.left, null, 14)
                    /  
                2 call(root.right, 2, 14)
                    \
                      19   (19>15, return false)
  
Complexity: Time O(n) Space O(n) 
补充： prefer 2nd approach, no worry about number boundary

public class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    public boolean helper(TreeNode head, long min,long max){
        if (head==null){return true;}
        if (head.val>min&&head.val< max)//BST feature
             return helper(head.left,min,head.val)&&helper(head.right,head.val,max);//越左越小，so max is 当前root, next左叶要小于它
        else return false;//or return false;
    }
}

其实只要正确place parent(root)的位置，余下值根据parent之前的来 

public class Solution {
    public boolean isValidBST(TreeNode root) {
        //need track low & high of subtree
        return helper(root, null, null);
    }
    
    public boolean helper(TreeNode root, TreeNode low, TreeNode high){
        if(root == null) return true;
        if(low != null && root.val <= low.val) return false;
        if(high != null && root.val >= high.val) return false;
        return helper(root.left, low, root) && helper(root.right, root, high);
    }
}

333. Largest BST Subtree

• Difficulty: Medium

https://leetcode.com/problems/largest-bst-subtree/

Company Microsoft

思路：Start from root and do an inorder traversal of the tree. For each node N, check whether the subtree rooted with N is BST or not. If BST, then return size of the subtree rooted with N. Else, recur down the left and right subtrees and return the maximum of values returned by left and right subtrees.

Time Complexity: The worst case time complexity of this method will be O(n^2). Consider a skewed tree for worst case analysis.

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