Leetcode 验证二叉搜索树

验证二叉搜索树

题目描述：

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

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

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

题目链接

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }

    private boolean helper(TreeNode root,long start,long end){
        if(root == null) return true;
        // 以下是范围判断
        if(root.val >= end || root.val <= start) return false;

        // // 以下是节点判断其实多余了，读者可以仔细思考
        // if(root.left != null && root.left.val >= root.val){
        //     return false;
        // }
        // if(root.right != null && root.right.val <= root.val){
        //     return false;
        // }

        return helper(root.left,start,root.val) && helper(root.right,root.val,end);
    }
}

定义方法helper(root,start,end)

为当前节点root作为根节点的值应该所在范围是否在(start,end)内

。然后返回值左子树满足搜索二叉树的定义并且右子树满足二叉搜索树。

详细请看代码，有疑问的地方欢迎留言。