0098.验证二叉搜索树

https://leetcode.cn/problems/validate-binary-search-tree/

方法一：递归

时间复杂度 $O(n)$，空间复杂度 $O(n)$，之所以空间复杂度为 $O(n)$ 是考虑到最坏情况下二叉树为一条链，树的高度为 $n$，递归最深达到 $n$ 层。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
	var dfs func(node *TreeNode, min, max int) bool
	dfs = func(node *TreeNode, min, max int) bool {
		if node == nil {
			return true
		}
		if node.Val <= min || node.Val >= max {
			return false
		}
		return dfs(node.Left, min, node.Val) && dfs(node.Right, node.Val, max)
	}
	return dfs(root, -1<<31-1, 1<<31)
}