Joey LIU | NANTSOU


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
/**
 * travel the binary search tree in inorder order so that the last value must be less than current one if it is valid binary search tree.
 * record the last value for the next recursive run.
 */
class Solution {
    private Integer lastVal = null;
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        // check root.left
        if (!isValidBST(root.left)) return false;
        
        // check root
        if (lastVal != null && lastVal >= root.val) return false;
        lastVal = root.val;
        
        // check root.right
        return isValidBST(root.right);
    }
}