LC98. 验证二叉搜索树

解题思路

这题使用中序遍历+辅助数组就能解决

中序遍历为(左->中->右)的遍历顺序

因为二叉搜索树的特性，我们使用中序遍历能使数组变得有序且是严格递增的。

只要数组不是严格递增我们就返回false

代码

Go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    nums := make([]int, 0, 0)
    dfs(root, &nums)
    for i := 1; i < len(nums); i++ {
        if nums[i] <= nums[i - 1]{ return false }
    }
    return true
}

func dfs(root *TreeNode, vec *[]int) {
    if root == nil {return}
    dfs(root.Left, vec)
    *vec = append(*vec, root.Val)
    dfs(root.Right, vec)
}