Leetcode 98. 验证二叉搜索树的两种方法

有效 二叉搜索树定义如下：

节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

因此，这道题，必须从最底部开始遍历。如果从上往下遍历的话，很容易让第三个定义不满足。

1.递归

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }

    public boolean isValidBST(TreeNode root,long lower,long upper) {
        if(root == null) return true;
        if(root.val >= upper || root.val <= lower) return false;
        return isValidBST(root.left,lower,root.val) && isValidBST(root.right,root.val,upper);
    }
}

2.用栈迭代

public boolean isValidBST(TreeNode root) {
    if(root==null) return true;
    Stack<TreeNode> stack = new Stack<TreeNode>();
    long lastVal = Long.MIN_VALUE;
    while(root!=null || !stack.isEmpty()){
        while(root!=null){
            stack.push(root);
            root=root.left;
        }
        root=stack.pop();
        if(lastVal >= root.val) return false;
        lastVal = root.val;
        root=root.right;
    }
    return true;