98. 验证二叉搜索树

题目描述:

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下:

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

示例 1:

输入:root = [2,1,3]
输出:true

示例 2:

输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4 。

提示:

  • 树中节点数目范围在[1, 10^4] 内
  • -2^31 <= Node.val <= 2^31 - 1

解题分析及思路:

这道题考察的是二叉树的遍历,不熟悉二叉树的遍历可以查看二叉树

这道题有关二叉搜索树

方法一:中序遍历

由于二叉搜索树的中序遍历本身就是一个递增的序列,所以可以通过中序遍历的方式来解决。

所以我们仅仅需要遍历一次二叉搜索树,然后将遍历的结果保存在一个数组中,然后判断数组是否是递增的即可。

func isValidBST(root *TreeNode) bool {
	var nums []int
	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}
		dfs(node.Left)
		nums = append(nums, node.Val)
		dfs(node.Right)
	}
	dfs(root)
	for i := 1; i < len(nums); i++ {
		if nums[i] <= nums[i-1] {
			return false
		}
	}
	return true
}

复杂度:

  • 时间复杂度:O(N),其中 N 是树中的节点个数
  • 空间复杂度:O(N),其中 N 是树中的节点个数

执行结果:

  • 执行耗时:3 ms,击败了86.13% 的Go用户
  • 内存消耗:6.1 MB,击败了7.58% 的Go用户

方法二:递归

我们可以通过递归的方式来解决这个问题,我们可以定义一个递归函数来判断当前节点是否是一个有效的二叉搜索树。

可以判断每个节点的左子树的最大值是否小于当前节点的值,右子树的最小值是否大于当前节点的值。

但是这样存在一个问题,那就是当右子树的左节点的值小于当前节点的值,这样就会导致右子树的最小值小于当前节点的值,所以我们需要引入一个最小值和最大值来解决这个问题。

  • 当遍历左子树时,我们需要将当前节点的值作为最大值传递给左子树
  • 当遍历右子树时,我们需要将当前节点的值作为最小值传递给右子树
func isValidBST(root *TreeNode) bool {
	var helper func(node *TreeNode, min *TreeNode, max *TreeNode) bool
	helper = func(node *TreeNode, min *TreeNode, max *TreeNode) bool {
		if node == nil {
			return true
		}
		if min != nil && node.Val <= min.Val {
			return false
		}
		if max != nil && node.Val >= max.Val {
			return false
		}
		return helper(node.Left, min, node) && helper(node.Right, node, max)
	}
	return helper(root, nil, nil)
}

复杂度:

  • 时间复杂度:O(N),其中 N 是树中的节点个数
  • 空间复杂度:O(1

执行结果:

  • 执行耗时:3 ms,击败了86.13% 的Go用户
  • 内存消耗:5.2 MB,击败了68.72% 的Go用户

通过次数 1M 提交次数 2.7M 通过率 38.6%

Related Posts

1026. 节点与其祖先之间的最大差值

## 题目描述:给定二叉树的根节点 root,找出存在于 不同 节点 A 和 B 之间的最大值 V,其中 V = |A.val - B.val|,且 A 是 B 的祖先。(如果 A 的任何子节点之一为 B,或者 A 的任何子节点是 B 的祖先,那么我们认为 A 是 B 的祖先)示例 1: ![](/img/leetcode/1026节点与其祖先之间的最大差值/tmp-tre

read more

1038. 从二叉搜索树到更大和树

## 题目描述:给定一个二叉搜索树 root (BST),请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。提醒一下, 二叉搜索树 满足下列约束条件:- 节点的左子树仅包含键 小于 节点键的节点。 - 节点的右子树仅包含键 大于 节点键的节点。 - 左右子树也必须是二叉搜索树。*示例 1:***![](/img/leetcode/

read more

105. 从前序与中序遍历序列构造二叉树

## 题目描述:给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。示例 1: ``` 输入: preorder = [3,9,20,15,7], inorder = [

read more

106. 从中序与后序遍历序列构造二叉树

## 题目描述:给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。示例 1: ``` 输入:inorder = [9,3,15,20,7], postorder

read more

109. 有序链表转换二叉搜索树

## 题目描述:给定一个单链表的头节点 head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树。本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。示例 1: ``` 输入: head = [-10,-3,0,5,9] 输出: [0,-3,9

read more

114. 二叉树展开为链表

## 题目描述:给你二叉树的根结点 root ,请你将它展开为一个单链表:- 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。 - 展开后的单链表应该与二叉树 先序遍历 顺序相同。示例 1: ``` 输入:root

read more