力扣 98. 验证二叉搜索树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
方案一：递归，遍历每一种可能。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isValidBST(root *TreeNode) bool {
// 开始递归，因为题目范围为 MinInt32～ MaxInt32，故而边界在 MinInt32 - 1, MaxInt32 + 1
return recur(root, math.MinInt32 - 1, math.MaxInt32 + 1)
}
// recur 递归函数，leftRange, rightRange 表示左右边界（非包含关系）
func recur(root *TreeNode, leftRange, rightRange int) bool {
if root == nil {
return true
}
if root.Val <= leftRange || root.Val >= rightRange {
return false
}
// 因为左子树只包含小于当前节点的数，右子树只包含大于当前节点的数
// 所以对左右子树的递归边界为当前节点的值
return recur(root.Left, leftRange, root.Val) &&
recur(root.Right, root.Val, rightRange)
}
- 时间复杂度：O(n)，n 为树中节点个数，因为需要遍历树中每个节点，所以时间复杂度为 O(n)。
- 空间复杂度：O(n)，n 为树中节点个数，树在最好情况下深度为 logn，最差情况下为 n，所以空间复杂度为 O(n)。