📑 题目：98. 验证二叉搜索树

🚀 本题 LeetCode 传送门

题目大意

给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征：

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

解题思路

  • 判断一个树是否是 BST，按照定义递归判断即可

代码

  1. package leetcode
  3. import ""math""
  5. /**
  6.  * Definition for a binary tree node.
  7.  * type TreeNode struct {
  8.  *     Val int
  9.  *     Left *TreeNode
  10.  *     Right *TreeNode
  11.  * }
  12.  */
  14. // 解法一，直接按照定义比较大小，比 root 节点小的都在左边，比 root 节点大的都在右边
  15. func isValidBST(root *TreeNode) bool {
  16.  return isValidbst(root, math.Inf(-1), math.Inf(1))
  17. }
  18. func isValidbst(root *TreeNode, min, max float64) bool {
  19.  if root == nil {
  20.   return true
  21.  }
  22.  v := float64(root.Val)
  23.  return v < max && v > min && isValidbst(root.Left, min, v) && isValidbst(root.Right, v, max)
  24. }
  26. // 解法二，把 BST 按照左中右的顺序输出到数组中，如果是 BST，则数组中的数字是从小到大有序的，如果出现逆序就不是 BST
  27. func isValidBST1(root *TreeNode) bool {
  28.  arr := []int{}
  29.  inOrder(root, &arr)
  30.  for i := 1; i < len(arr); i++ {
  31.   if arr[i-1] >= arr[i] {
  32.    return false
  33.   }
  34.  }
  35.  return true
  36. }
  38. func inOrder(root *TreeNode, arr *[]int) {
  39.  if root == nil {
  40.   return
  41.  }
  42.  inOrder(root.Left, arr)
  43.  *arr = append(*arr, root.Val)
  44.  inOrder(root.Right, arr)
  45. }