LeetCode 98. 验证二叉搜索树 做题小结

题目：

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

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

输入:
    2
   / \
  1   3
输出: true
示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

代码：

1，使用递归

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

2，用栈实现

import java.util.Stack;
class Solution {
    public boolean isValidBST(TreeNode root) {
		TreeNode p = root;
        TreeNode b = null;
		Stack<TreeNode> myStack = new Stack<TreeNode>();
		while (p != null || !myStack.isEmpty()) {
			if (p != null) {
				myStack.push(p);
				p = p.left;
			} else {
				p = myStack.pop();
				if(b!=null && p.val<=b.val){
                    return false;
                }
                b = p;
				p = p.right;
			}
		}
        return true;
    }
}