题目链接：LeetCode 98. 验证二叉搜索树

题意：

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

解题思路：

递归法1

由二叉搜索树的性质可知，中序遍历的结果是有序的，因此可以利用这个性质来判断当前二叉树是否是二叉搜索树。

代码：

var res []int //存放二叉树中所有节点中序遍历的值 
func isValidBST(root *TreeNode) bool {
    res = []int{}
    dfs(root)
    for i:=1;i<len(res);i++{
        if res[i] <= res[i-1]{
            return false
        }
    }
    return true
}
func dfs(root *TreeNode){
    if root == nil {
        return 
    }
    dfs(root.Left)
    res = append(res,root.Val)
    dfs(root.Right)
}

这道题目比较容易陷入两个陷阱：

陷阱1
不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。

写出了类似这样的代码：

if (root->val > root->left->val && root->val < root->right->val) {
    return true;
} else {
    return false;
}

我们要比较的是 左子树所有节点小于中间节点，右子树所有节点大于中间节点。所以以上代码的判断逻辑是错误的。
陷阱2
样例中最小节点 可能是int的最小值，如果这样使用最小的int来比较也是不行的。

此时可以初始化比较元素为longlong的最小值。

递归法2

中序遍历二叉树，判断当前节点的值是否严格大于前一个结点

func isValidBST(root *TreeNode) bool {
    var pre *TreeNode // 用来记录中序遍历时的前一个节点
    var travel func(root *TreeNode)bool

    travel = func(root *TreeNode)bool{
        if root == nil {
            return true
        }
        left := travel(root.Left)

        if pre != nil && pre.Val >= root.Val{
            return false
        } 
        pre = root; 
        right := travel(root.Right)
        return left && right
    }
    return travel(root)
}

LC示例代码

func isValidBST(root *TreeNode) bool {
    // 由题目中的数据限制可以得出min和max
    return check(root,math.MinInt,math.MaxInt)
}

func check(node *TreeNode,min,max int) bool {
    // 二叉搜索树也可以是空树
    if node == nil {
        return true
    }
    if min >= node.Val || max <= node.Val {
        return false
    }
    // 分别对左子树和右子树递归判断，如果左子树和右子树都符合则返回true
    return check(node.Right,node.Val,max) && check(node.Left,min,node.Val)
}