leetcode 98 Validate Binary Search Tree

Problem:

Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Example 1:

    2
   / \
  1   3

Binary tree [2,1,3], return true.
Example 2:

    1
   / \
  2   3

Binary tree [1,2,3], return false.

解题思路

一开始想当然用递归的思想，如果左子树的值小于根节点且同时又满足右子树的值大于根节点，就继续递归，否则返回false。代码如下。

public class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root==null){
            return true;
        }
        if(root.left!=null && (root.left.val>root.val || !isValidBST(root.left))){
            return false;
        }
        
        if(root.right!=null && (root.right.val<root.val || !isValidBST(root.right))){
            return false;
        }
        return true;
    }
}```
但是运行后发现了问题。这段代码中我只关心了某一个节点是否符合要求。而纵观全局，所有的根节点右边的数字都应该大于根节点。思考之后，我设立一个取值范围，用于递归中。

public boolean isValidBST(TreeNode root) {
if(root==null)
return true;

return helper(root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY);

}

public boolean helper(TreeNode root, double low, double high){

if(root.val<=low || root.val>=high)
    return false;

if(root.left!=null && !helper(root.left, low, root.val)){
    return false;
}

if(root.right!=null && !helper(root.right, root.val, high)){
    return false;
}

return true;    

}

第三种方法写起来更简单，但是如果错误就发生在根节点附近，那它要慢于第二种的速度。

public boolean isValidBST(TreeNode root) {
return isValidBST(root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY);
}

public boolean isValidBST(TreeNode p, double min, double max){
if(p==null)
return true;

if(p.val <= min || p.val >= max)
    return false;

return isValidBST(p.left, min, p.val) && isValidBST(p.right, p.val, max);

}

以上都是用的递归的思想来解决问题，现在利用广度优先遍历的思想来解决。
广度优先搜索算法需要用到队列。具体请参考以下链接：

public class Solution {
public boolean isValidBST(TreeNode root) {
if(root == null)
return true;
//利用一个队列来存储节点。
LinkedList<BNode> queue = new LinkedList<BNode>();
//初始化调用，根节点的取值范围是负无穷到正无穷
queue.add(new BNode(root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY));
while(!queue.isEmpty()){
//从队列里弹出一个节点
BNode b = queue.poll();
if(b.n.val <= b.left || b.n.val >=b.right){
return false;
}
if(b.n.left!=null){
//添加一个新的节点。
queue.offer(new BNode(b.n.left, b.left, b.n.val));
}
if(b.n.right!=null){
queue.offer(new BNode(b.n.right, b.n.val, b.right));
}
}
return true;
}
}
//define a BNode class with TreeNode and it's boundaries
class BNode{
TreeNode n;
double left;
double right;
public BNode(TreeNode n, double left, double right){
this.n = n;
this.left = left;
this.right = right;
}
}

#leetcode 333 [Largest BST Subtree](https://leetcode.com/problems/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 descendants.Here's an example:

10
/ \

5 15
/ \ \
1 8 7

The Largest BST Subtree in this case is the highlighted one(5,1,8. The return value is the subtree's size, which is 3.
 
Hint:
You can recursively use algorithm similar to [98. Validate Binary Search Tree](https://leetcode.com/problems/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 Wrapper{
int size;
int lower, upper;
boolean isBST;

public Wrapper(){
    lower = Integer.MAX_VALUE;
    upper = Integer.MIN_VALUE;
    isBST = false;
    size = 0;
}

}
public class Solution {
public int largestBSTSubtree(TreeNode root) {
return helper(root).size;
}

public Wrapper helper(TreeNode node){
    Wrapper curr = new Wrapper();

    if(node == null){
        curr.isBST= true;
        return curr;
    }

    Wrapper l = helper(node.left);
    Wrapper r = helper(node.right);

    //current subtree's boundaries
    curr.lower = Math.min(node.val, l.lower);
    curr.upper = Math.max(node.val, r.upper);

    //check left and right subtrees are BST or not
    //check left's upper again current's value and right's lower against current's value
    if(l.isBST && r.isBST && l.upper<=node.val && r.lower>=node.val){
        curr.size = l.size+r.size+1;
        curr.isBST = true;
    }else{
        curr.size = Math.max(l.size, r.size);
        curr.isBST  = false;
    }

    return curr;
}

}