98.验证二叉搜索树

输入：root =[5,4,6,null,null,3,7] 输出：false

1. 二叉搜索树是根节点小于左子树所有节点且大于右子树所有节点，因此不能仅仅判断根节点和左孩子和右孩子的大小关系。第一次写的时候做法是，先递归查左子树和右子树是否是二叉搜索树，若不是则可以之间返回false。如果子树满足则查当前树是否满足，方法是判断根节点是否比左孩子的最右边一排节点都大，比右孩子最左边一排节点都小。这里不需要判断左孩子的左孩子的最右边一排(因为左孩子已经判断过)。每个节点最多被判断一次，时间O(n)。

 public boolean dfs(TreeNode root)
    {
        if(root.left!=null&&dfs(root.left)==false)
        return false;
        if(root.right!=null&&dfs(root.right)==false)
        return false;
        TreeNode leftchild=root.left,rightchild=root.right;
        TreeNode lright,rleft;
        if(leftchild!=null)
        {
            if(leftchild.val>=root.val)
            return false;
            lright=leftchild.right;
            while(lright!=null)
            {
                if(lright.val>=root.val)
                return false;
                lright=lright.right;
            }
        }
        if(rightchild!=null)
        {
            if(rightchild.val<=root.val)
            return false;
            rleft=rightchild.left;
            while(rleft!=null)
            {
                if(rleft.val<=root.val)
                return false;
                rleft=rleft.left;
            }
        }
        return true;
    }

2. 第二种思路是一种自顶向下的递归，用区间来判断大小关系，dfs(root,low,high)中low表示root的节点的下界，high表示上界。如果root在区间内说明这个点符合以上层的二叉搜索树定义，但是下层的还不知道，递归左子树时上界设为root.val，递归右子树下界设为root.val。这种方法比较难想也比较打破常规的地方在于，根节点值与左孩子右孩子大小关系的比较交给孩子节点来进行。区间限制的是上层的树，往下层进行更新。

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