扣初级算法-24-树-验证二叉搜索树

学习目标：

本次学习目标为 力扣初级算法-树，其中主要的LC如下：

• 验证二叉搜索树

学习内容：

解题思路：

• 解法一： 直接递归

• 解题思路：

  • 如果一个结点是空的，我们默认他是有效的二叉搜索树。
  • 否则如果左节点不为空，我们要判断是否大于左节点的值。
  • 如果右节点不为空，我们还要判断小于右节点的值。
  • 但是这里会有一个问题，就是不通层的树，会存在小当前 root节点，但是比 root 的节点的root节点还小，这里是会有问题的。
  • 故需要分别以左右两个子节点分别判断
  • 左子树范围的最小值是minVal，最大值是当前节点的值，也就是root的值，因为左子树的值要比当前节点小
  • 右子数范围的最大值是maxVal，最小值是当前节点的值，也就是root的值，因为右子树的值要比当前节点大

• 代码实现：

/**
	 * 二叉搜索树 ： 是指 每个节点左子树的值都比当前节点小，右子树的值都比当前节点大
	 * 解法一：递归  错误写法
	 */
	public boolean isValidBST00(TreeNode root) {
		if (null == root){
			return true;
		}
		if (root.left != null &&  root.val <= root.left.val || root.right !=null && root.val >= root.right.val){
			return false;
		}

		return isValidBST00(root.left) && isValidBST00(root.right);

	}


	/**
	 *
	 * 解法一：递归
	 */
	public boolean isValidBST(TreeNode root) {

		return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);

	}

	public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
		if (root == null){
			return true;
		}
		//每个节点如果超过这个范围，直接返回false
		if (root.val >= maxVal || root.val <= minVal){
			return false;
		}
		//这里再分别以左右两个子节点分别判断，
		//左子树范围的最小值是minVal，最大值是当前节点的值，也就是root的值，因为左子树的值要比当前节点小
		//右子数范围的最大值是maxVal，最小值是当前节点的值，也就是root的值，因为右子树的值要比当前节点大
		return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
	}