给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
代码语言：javascript复制输入:
2
/
1 3
输出: true示例 2:
代码语言：javascript复制输入:
5
/
1 4
/
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。解题思路：
1，中序遍历
代码语言：javascript复制/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
var last=^(int(^uint(0) >> 1))
func isValidBST(root *TreeNode) bool {
if root!=nil{
if!isValidBST(root.Left){
return false
}
if last>=root.Val{
return false
}
last=root.Val
if !isValidBST(root.Right){
return false
}
}
return true
}方法二：
递归：根节点>大于左节点最大值，小于右节点最小值
代码语言：javascript复制/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isValidBST(root *TreeNode) bool {
if root==nil{
return true
}
if root.Left!=nil&& root.Right!=nil{
l:=maxBST(root.Left)
r:=minBST(root.Right)
return isValidBST(root.Left)&&isValidBST(root.Right)&&l<root.Val && root.Val<r
}
if root.Left!=nil{
l:=maxBST(root.Left)
return isValidBST(root.Left)&&l<root.Val
}
if root.Right!=nil{
r:=minBST(root.Right)
return isValidBST(root.Right)&&root.Val<r
}
return true
}
func maxBST(root *TreeNode)int{
if root.Right!=nil{
return maxBST(root.Right)
}
return root.Val
}
func minBST(root *TreeNode)int{
if root.Left!=nil{
return minBST(root.Left)
}
return root.Val
}
