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.

解題思路

一開始想當(dāng)然用遞歸的思想，如果左子樹的值小于根節(jié)點(diǎn)且同時又滿足右子樹的值大于根節(jié)點(diǎn)，就繼續(xù)遞歸，否則返回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;
    }
}```
但是運(yùn)行后發(fā)現(xiàn)了問題。這段代碼中我只關(guān)心了某一個節(jié)點(diǎn)是否符合要求。而縱觀全局，所有的根節(jié)點(diǎn)右邊的數(shù)字都應(yīng)該大于根節(jié)點(diǎn)。思考之后，我設(shè)立一個取值范圍，用于遞歸中。

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;    

}

第三種方法寫起來更簡單，但是如果錯誤就發(fā)生在根節(jié)點(diǎn)附近，那它要慢于第二種的速度。

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);

}

以上都是用的遞歸的思想來解決問題，現(xiàn)在利用廣度優(yōu)先遍歷的思想來解決。
廣度優(yōu)先搜索算法需要用到隊列。具體請參考以下鏈接：

public class Solution {
public boolean isValidBST(TreeNode root) {
if(root == null)
return true;
//利用一個隊列來存儲節(jié)點(diǎn)。
LinkedList<BNode> queue = new LinkedList<BNode>();
//初始化調(diào)用，根節(jié)點(diǎn)的取值范圍是負(fù)無窮到正無窮
queue.add(new BNode(root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY));
while(!queue.isEmpty()){
//從隊列里彈出一個節(jié)點(diǎn)
BNode b = queue.poll();
if(b.n.val <= b.left || b.n.val >=b.right){
return false;
}
if(b.n.left!=null){
//添加一個新的節(jié)點(diǎn)。
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;
}

}