98. 验证二叉搜索树

题目

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

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

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

示例 1：

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

示例 2：

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

提示：

• 树中节点数目范围在[1, 10⁴] 内
• -2³¹ <= Node.val <= 2³¹ - 1

题解

使用二叉树中序遍历，如果前一个节点值比后一个大，则不满足二叉搜索树规则。

代码实现

var pre *TreeNode

// 中序遍历，如果前一个节点比后一个值大，则返回 false
func isValidBST(root *TreeNode) bool {
	pre = nil
	return inorderBST(root)
}

func inorderBST(root *TreeNode) bool {
	if root == nil {
		return true
	}

	left := inorderBST(root.Left)

	if pre != nil {
        preVal := pre.Val
		pre = root
		if preVal >= root.Val {
			return false
		}
		
	}
    pre = root
    
	right := inorderBST(root.Right)
	return left && right
}