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

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

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

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

解析

递归或者中序遍历，递归好理解很多。

//递归，我们用null来表达最大最小值是很明智的
class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(root.left,null,root.val) && helper(root.right,root.val,null);
    }
    public boolean helper(TreeNode head,Integer min,Integer max){
        if(head==null) return true;
        return ( (min==null)||(head.val>min) ) && ((max==null)||(head.val < max)) && helper(head.left,min,head.val) && helper(head.right,head.val,max);
    }
}

//BFS 中序遍历
class Solution {
    public boolean isValidBST(TreeNode root) {
        //迭代
        if(root==null) return true;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode head = root;
        TreeNode pre = null;
        while(!stack.isEmpty()||head!=null){
            while(head!=null){
                stack.push(head);
                head = head.left;
            }
            head = stack.pop();
            if(pre!=null && pre.val>=head.val){
                return false;
            }
            pre = head;
            if(head.right!=null){
                head = head.right;
            }else{
                head = null;
            }
        }
        return true;
    }
}

注意：本文归作者所有，未经作者允许，不得转载