8.18验证二叉搜索树 - WisperDin/blog GitHub Wiki

描述

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

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

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

示例 1:

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

示例 2:

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

思路

要判断树是二叉搜索树，第一想法可能会误入陷阱，递归的去判断，对每个子树，其左孩子小于根节点，右孩子大于根节点。

但这是错误的，再仔细思考二叉搜索树定义可知，对每一个子树，其左子树全部节点小于根节点，右子树全部节点大于根节点，即不能局部的判断一个子树是否为二叉搜索树

通过几个用例分析

    10
   / 
  8   
 /
a
其中a<8
    10
     \
      15
      /
     b
其中b<15 && b>10

    10
   / 
  8   
   \
    c
  其中c>8 c<10
    
    10
     \
      15
        \
         d
     其中 d>15

即对任意一个节点A来说，

  • 其左子树任意节点的最大取值为 A.Val - 1 （限制左子树的最大值）
  • 其右子树任意节点的最小取值为 A.Val + 1 （限制右子树的最小值）

这种即二叉搜索树规则的另一种表述，但实现方式则更具体

实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func bstRecursive(root *TreeNode, min int, max int) bool {
    if root == nil {
        return true
    }
    if root.Left == nil && root.Right == nil {
        return true
    }
    if root.Right == nil {
        if !bstRecursive(root.Left,min,root.Val-1) {
            return false
        }
        return root.Left.Val >= min && root.Left.Val <= max && root.Left.Val<root.Val
    }
    if root.Left == nil {
        if !bstRecursive(root.Right,root.Val+1,max) {
            return false
        }
        return root.Right.Val >= min && root.Right.Val <= max  && root.Right.Val>root.Val
    }
    
    if !bstRecursive(root.Right,root.Val+1,max) || !bstRecursive(root.Left,min,root.Val-1) {
        return false
    }
    return root.Left.Val >= min && root.Left.Val <= max && root.Right.Val >= min && root.Right.Val <= max && root.Left.Val<root.Val && root.Right.Val>root.Val
}

func isValidBST(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return bstRecursive(root,math.MinInt32,math.MaxInt32)
}
⚠️ **GitHub.com Fallback** ⚠️