[Leetcode] 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.

判断一棵树是否是二叉搜索树，根据定义，根比左子树所有的节点都大，比右子树所有的节点都小。我们可以利用二叉搜索树的性质：中序遍历为严格递增来判断一颗树是否合法。使用Morris遍历同时保持上一个遍历的节点，可以达到时间复杂度O(n)空间复杂度O(1)的方法。

    public boolean isValidBST(TreeNode root) {
        TreeNode pre = null, cur = root, tmp;
        while(cur != null) {
            if(cur.left == null) {
                if(pre != null && pre.val >= cur.val) 
                    return false;
                pre = cur;
                cur = cur.right;
            }
            else {
                tmp = cur.left;
                while(tmp.right != null && tmp.right != cur)
                    tmp = tmp.right;
                if(tmp.right == null) {
                    tmp.right = cur;
                    cur = cur.left;
                }
                else {
                    tmp.right = null;
                    if(pre != null && pre.val >= cur.val) 
                        return false;
                    pre = cur;
                    cur = cur.right;
                }
            }
        }
        return true;
    }

另一方面，我们也可以使用递归求解，但是在递归的时候不能简单的判断根与左右子树的节点的大小，而必须判断根是否在一个范围以内(min, max)，在递归调用的时候，先判断当前的根是否在范围内，然后递归的时候左子树的max变为当前根的值，右子树的min变成当前根的值，这样保证区间合法，然后判断左右子树是否合法。这种方法的时间复杂度同样是O(n)，但是空间复杂度大概为O(logn)。

    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    
    private boolean isValidBST(TreeNode root, int min, int max) {
        if(root == null)
            return true;
        if(root.val > min && root.val < max && isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max))
            return true;
        return false;
    }