给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3]
输出：true示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。提示：
- 树中节点数目范围在[1, 104] 内
- -2^31 <= Node.val <= 2^31 – 1
解题：
func isValidBST(root *TreeNode) bool {
var r []int
var dfs func(node *TreeNode) bool
dfs = func(node *TreeNode) bool {
if node == nil {
return true
}
left := dfs(node.Left)
l := len(r)
if l > 0 && node.Val <= r[l-1] {
return false
}
r = append(r, node.Val)
right := dfs(node.Right)
return left && right
}
return dfs(root)
}官方解答：
1.递归
func isValidBST(root *TreeNode) bool {
return helper(root, math.MinInt64, math.MaxInt64)
}
func helper(root *TreeNode, lower, upper int) bool {
if root == nil {
return true
}
if root.Val <= lower || root.Val >= upper {
return false
}
return helper(root.Left, lower, root.Val) && helper(root.Right, root.Val, upper)
}2.中序遍历
func isValidBST(root *TreeNode) bool {
var stack []*TreeNode
inorder := math.MinInt64
for len(stack) > 0 || root != nil {
for root != nil {
stack = append(stack, root)
root = root.Left
}
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
if root.Val <= inorder {
return false
}
inorder = root.Val
root = root.Right
}
return true
}