LeetCode-098-验证二叉搜索树 LeetCode-098-验证二叉搜索树

验证二叉搜索树

题目描述：给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。

节点的右子树只包含大于当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

示例说明请见LeetCode官网。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：递归法

【LeetCode-098-验证二叉搜索树】根据二叉搜索树的性质，当前节点左子树的上边界（不包含）和右子树的下边界（不包含）是当前节点的值，所以可以用递归的方法来解决，递归过程如下：

根节点没有父结点，所以第一次调用递归方法上下边界使用最大最小值；

如果当前节点为null，说明是叶子节点，直接返回true；

如果当前节点的值不在上下边界范围内，返回false；

递归判断当前节点的左右节点是否在相应的上线边界范围内。

import com.kaesar.leetcode.TreeNode; public class LeetCode_098 { /** * 递归法 * * @param root * @return */ public static boolean isValidBST(TreeNode root) { return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE); }/** * 递归方法 * * @param node 当前节点 * @param low当前节点的下边界（不包含） * @param high 当前节点的上边界（不包含） * @return */ private static boolean isValidBST(TreeNode node, long low, long high) { // 如果node为null，说明是叶子节点，直接返回true if (node == null) { return true; } // 如果当前节点的值不在上下边界范围内，返回false if (node.val <= low || node.val >= high) { return false; }// 递归判断当前节点的左右节点是否在相应的上线边界范围内 return isValidBST(node.left, low, node.val) && isValidBST(node.right, node.val, high); }public static void main(String[] args) { TreeNode root = new TreeNode(5); root.left = new TreeNode(1); root.right = new TreeNode(4); root.right.left = new TreeNode(3); root.right.right = new TreeNode(6); System.out.println(isValidBST(root)); } }