验证二叉搜索树

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees must also be binary search trees. Example 1:

  2
 / \
1   3

Input: [2,1,3] Output: true Example 2:


    5
   / \
  1   4
     / \
    3   6

Input: [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.

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

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

解题思路

  • 递归法
    • 检查每个节点，左节点是否小于根节点，右节点大于根节点
  • 中序遍历法
    • 正确的二叉搜索树，按中序遍历，是按左、中、右顺序从小到大排序，如果出现逆序则不是正确的二叉搜索树
func isValidBST(root *TreeNode) bool {
      return Helper(root, math.MinInt32, math.MaxInt32)
 }
 
 func Helper(root *TreeNode, min, max int) bool {
      if root == nil {
          return true
      }
 
      if root.Val < min || root.Val > max {
          return false
      }

     return Helper(root.Left, min, root.Val-1) && Helper(root.Right, root.Val+1, max)
}