98 Validate Binary Search Tree

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.

思路1: inorder traversal

用inoreder traversal去遍历所有点，check现在访问的点是否比上次访问的点大。

实现关键

1.需要定义一个lastAccess来指向上次访问的节点，必须是对于sol class的instance variable，这样在每一次递归中都能使用。

2.对于第一个访问的节点，lastAccess ==null，不做任何比较，用lastAccess指向该节点

3.递归：

base：root == null 返回true

recursive（中序遍历）：

1）调用自身检查左子节点，若不满足，直接返回false

2）左子节点满足后，访问当前节点，与上一个访问的节点比较，若不满足，直接返回false;若满足，lastAccess指向当前节点；

3）当前节点满足后，调用自身检查右子节点，若不满足，直接返回false

4）左，自身，右都慢足，说明以当前节点为root的tree是BST，返回true

4.由于不能出现duplicate node，因此用<=来判断出返回false的情况

public class Solution {

    private TreeNode lastAccess = null;

    public boolean isValidBST(TreeNode root) {

        //base case
        if(root == null) return true;

        //recursive
        //left
        if(!isValidBST(root.left)) return false;
        //access(compare to last access)
        if(lastAccess == null) lastAccess = root;
        else {
            if(root.val <= lastAccess.val) {
                return false;
            }
            else {
                lastAccess = root;
            }
        }
        //right
        if(!isValidBST(root.right)) return false;

        return true;
    }

}

复杂度：

时间复杂度O(N)，因为访问每个点各一次，递归调用函数的时间可以忽略

思路2：每个node的上下边界

递归函数传入3个参数（当前节点，上边界，下边界）

实现关键：

1.min，max是Integer型，最初为null

2.递归：

base case：root == null，返回true

recursive（对每个检查是否满足上下边界）：

1）如果上、下都有边界，上下都比较，若不满足直接返回false

2）如果只有下边界，下边界比较，若不满足直接返回false

3）如果只有上边界，上边界比较，若不满足直接返回false

4）当前节点满足之后，调用自身检查左子节点与右子节点是否满足

3.由于不能出现duplicate node，因此用<=或>=来判断出返回false的情况

public class Solution {

    public boolean isValidBST(TreeNode root) {

        return helper(root, null, null);
    }

    private boolean helper(TreeNode root, Integer min, Integer max) {

        //base case
        if(root == null) return true;
        //recursive
        //check current root
        if(min != null && max != null) {
            if( (root.val <= min) || (root.val >= max) ) return false;
        }
        else if(min != null) {
            if(root.val <= min) return false;    
        } 
        else if(max != null) {
            if(root.val >= max) return false;
        }
        else {}
        return helper(root.left, min, root.val) && helper(root.right, root.val, max);
    }
}

复杂度

因为对以每一个节点，只访问一次，最多访问完全部节点，因此O(N)