题目
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
递归
如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。
时间复杂度 : O(n) 空间复杂度：O(n)
中序遍历
二叉搜索树保证了左子树的节点的值均小于根节点的值，根节点的值均小于右子树的值，因此中序遍历以后得到的序列一定是升序序列
时间复杂度 : O(n) 空间复杂度：O(n)
助解：假设现在有二叉树 5
/ \
3 6
先遍历所有左节点，全部放入栈中 stack = [5,3]
遍历完所有左节点后 从栈中取出 3 stack = [5]
判断是否小于 变量inorder 用于保存中序节点val
inorder初始化的值为min，所以不可能小
inorder赋值3
把节点root=root.right(nil) 继续下一次循环
root=3的节点没有右节点，所以跳过压入栈循环
再次从栈中pop节点 5 stack = []
判断节点5(中节点)是否小于3(左节点)，不小于说明符合有序二叉树
inorder赋值5
把节点root=root.right(6) 继续下一次循环
节点6不为空，压入栈中 stack = [6]
root = root.left 由于节点6没有子节点了，进入下一步
把节点6从栈中取出 stack = []
判断节点6(右节点)是否小于5(中节点)，不小于说名符合有序二叉树
把节点root=root.right(nil) 继续下一次循环
栈为空,root为nil,不满足最外层循环条件,程序结束 返回true
代码
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// 递归
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
}
// 左节点：如果左节点大于等于根节点 false
// 右节点：如果右节点小于等于跟节点 false
if root.Val <= lower || root.Val >= upper{
return false
}
// 递归左右节点
return helper(root.Left,lower,root.Val) && helper(root.Right,root.Val,upper)
}
// 中序遍历
func isValidBST2(root *TreeNode) bool {
// 栈保存节点
stack := []*TreeNode{}
inorder := math.MinInt64
// 当栈所有节点被取出 以及 节点为空时结束循环
for len(stack) > 0 || root != nil{
// 先把所有节点压入栈
for root != nil{
stack = append(stack,root)
root = root.Left
}
// pop栈，判断是否符合有序二叉树
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
if root.Val <= inorder{
return false
}
// 保存根节点值，切换到右子树
inorder = root.Val
root = root.Right
}
return true
}