验证二叉搜索树

0x01.问题

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

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

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

示例 1:

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

示例 2:

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

 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * 

0x02.解决思路

• 把二叉搜索树抽象出来满足一个条件就是：每个节点都大于左左节点，小于右节点。（左右子树非空的情况下）
• 所以我们只需要在遍历的时候去判断每个节点是否满足就行了。
• 递归下遍历的方式不限，这里使用前序遍历。

具体算法：

• 设计递归函数helper，参数为node，low，up，node为当前需要判断的节点，low为左边界，up为右边界，初始时都为空。
• 如果node为空，说明到达了叶子节点，直接返回true。
• 如果low和up不为空，且node.val不在这个范围之内，返回false。否则进行下面的递归。
• 递归判断右子树是否满足条件：low更新为node.val，up还是up。
• 递归判断左子树是否满足条件：low还是low，up更新为node.val。

0x03.解决代码

class Solution {
    private boolean helper(TreeNode node,Integer low,Integer up){
        if(node==null){
            return true;
        }
        if((low!=null&&node.val<=low)||(up!=null&&node.val>=up)){
            return false;
        }
        return helper(node.right,node.val,up)&&helper(node.left,low,node.val);
    }
    public boolean isValidBST(TreeNode root) {
        return helper(root,null,null);
    }
}

ATFWUS --Writing By 2020–05-05