validate-binary-search-tree.md

98. Validate Binary Search Tree - 验证二叉搜索树

Tags - 题目标签

Description - 题目描述

EN:

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

A valid 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:

Input: root = [2,1,3]
Output: true

Example 2:

Input: root = [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.

 

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -231 <= Node.val <= 231 - 1

ZH-CN:

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

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

 

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

 

提示：

• 树中节点数目范围在[1, 104] 内
• -231 <= Node.val <= 231 - 1

Link - 题目链接

LeetCode - LeetCode-CN

Latest Accepted Submissions - 最近一次 AC 的提交

Language	Runtime	Memory	Submission Time
golang	4 ms	5 MB	2022/06/07 13:35

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
  var pre int = - 2 << 32
  var inOrder func (root * TreeNode) bool
  inOrder = func (root * TreeNode) bool {
    if root == nil {
      return true
    }
    left := inOrder(root.Left)

    if root.Val <= pre {
      return false
    }

    pre = root.Val

    right := inOrder(root.Right)

    return left && right
  }

  return inOrder(root)

}

My Notes - 我的笔记

思路： 二叉搜索树的中序遍历序列是一个递增排序序列。 递归中序遍历，用 pre 存储上一个中序遍历的值，若当前值小于或等于上一个值（即当前值不满足在中序遍历序列中比上一个值大），则该二叉树不是二叉搜索树。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
  var pre int = - 2 << 32
  var inOrder func (root * TreeNode) bool
  inOrder = func (root * TreeNode) bool {
    if root == nil {
      return true
    }
    left := inOrder(root.Left)

    if root.Val <= pre {
      return false
    }

    pre = root.Val

    right := inOrder(root.Right)

    return left && right
  }

  return inOrder(root)

}