98. 验证二叉搜索树

题目描述

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

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

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

示例 1：

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

示例 2：

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

提示：

• 树中节点数目范围在[1, 104] 内
• -231 <= Node.val <= 231 - 1

解题思路

二叉搜索树的特点是左子树的值都小于根节点，右子树的值都大于根节点。所以可以使用递归来验证每个节点是否满足这个条件。

一开始想的是：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
	if root == nil {
		return true
	}

	if root.Left != nil {
		if root.Left.Val >= root.Val || !isValidBST(root.Left) {
			return false
		}
	}

	if root.Right != nil {
		if root.Right.Val <= root.Val || !isValidBST(root.Right) {
			return false
		}
	}

	return true
}

结果没有过，因为没有考虑到子树的值范围。当出现 [5,4,6,null,null,3,7] 这种情况时，左子树的值 4 小于根节点 5，但右子树的值 3 小于根节点 5。

结合二叉搜索树的特性，特别适合中序遍历来解决这个问题。中序遍历的结果是一个有序的数组，我们只需要检查这个数组是否是严格递增的。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
	inorder := []int{}
	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}

		dfs(node.Left)
		inorder = append(inorder, node.Val)
		dfs(node.Right)
	}
	dfs(root)

	for i := 1; i < len(inorder); i++ {
		if inorder[i] <= inorder[i-1] {
			return false
		}
	}

	return true
}

这种方法的时间复杂度是 O(n)，空间复杂度也是 O(n)。可以使用递归来优化空间复杂度。在递归过程中，维护一个前一个节点的指针，检查当前节点的值是否大于前一个节点的值。

func isValidBST(root *TreeNode) bool {
	var prev *TreeNode = nil
	var dfs func(node *TreeNode) bool
	dfs = func(node *TreeNode) bool {
		if node == nil {
			return true
		}

		if !dfs(node.Left) {
			return false
		}

		if prev != nil && node.Val <= prev.Val {
			return false
		}
		prev = node

		return dfs(node.Right)

	}

	return dfs(root)
}