98. 验证二叉搜索树

题目#

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

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

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
    根节点的值为 5 ，但是其右子节点值为 4 。

思路#

递归处理可能会遇到 edge case，所以我们进行一个中序遍历，验证结果数组是不是严格递增即可。

代码#

func isValidBST(root *TreeNode) bool {
    res := []int{}
    inOrder(root, &res)

    // 验证是否严格递增
    for i := 0; i < len(res)-1; i++ {
        if res[i] >= res[i+1] {
            return false
        }
    }
    return true
}

// 进行中序遍历
func inOrder(root *TreeNode, result *[]int) {
    if root == nil {
        return
    }

    inOrder(root.Left, result)
    *result = append(*result, root.Val)
    inOrder(root.Right, result)
}