leetcode地址：验证二叉搜索树
给你一个二叉树的根节点 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
实现思路
这个问题要求判断一棵二叉树是否是一个有效的二叉搜索树（BST）。二叉搜索树的定义如下：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
为了验证一棵二叉树是否是BST，我们可以使用中序遍历的方法。对于BST，中序遍历应该产生一个严格递增的序列。
递归验证
设定当前节点的上下界，初始时根节点的上下界分别为负无穷大和正无穷大。
如果当前节点的值不在上下界之间，则该树不是BST。
递归检查左子树，更新上界为当前节点值；递归检查右子树，更新下界为当前节点值。
中序遍历
使用中序遍历，检查遍历过程中前一个节点的值是否小于当前节点的值。如果不满足，则该树不是BST。
代码详解
# 定义二叉树节点类
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 递归验证函数
def isValidBST(root: TreeNode) -> bool:
def validate(node, low=float('-inf'), high=float('inf')):
if not node:
return True
if not (low < node.val < high):
return False
return validate(node.left, low, node.val) and validate(node.right, node.val, high)
return validate(root)
# 中序遍历验证函数
def isValidBSTInorder(root: TreeNode) -> bool:
stack, inorder = [], float('-inf')
while stack or root:
while root:
stack.append(root)
root = root.left
root = stack.pop()
if root.val <= inorder:
return False
inorder = root.val
root = root.right
return True
# 测试示例
root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)
print(isValidBST(root)) # 输出: True
print(isValidBSTInorder(root)) # 输出: True
go实现
package main
import (
"fmt"
"math"
)
// TreeNode is a binary tree node.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// validate function for recursive check
func validate(node *TreeNode, low, high int) bool {
if node == nil {
return true
}
if node.Val <= low || node.Val >= high {
return false
}
return validate(node.Left, low, node.Val) && validate(node.Right, node.Val, high)
}
// isValidBST checks if a binary tree is a valid BST
func isValidBST(root *TreeNode) bool {
return validate(root, math.MinInt64, math.MaxInt64)
}
// inOrderTraversal function for in-order traversal check
func inOrderTraversal(node *TreeNode, prev *int) bool {
if node == nil {
return true
}
if !inOrderTraversal(node.Left, prev) {
return false
}
if node.Val <= *prev {
return false
}
*prev = node.Val
return inOrderTraversal(node.Right, prev)
}
// isValidBSTInOrder checks if a binary tree is a valid BST using in-order traversal
func isValidBSTInOrder(root *TreeNode) bool {
prev := math.MinInt64
return inOrderTraversal(root, &prev)
}
// Helper function to print the tree in-order
func printInOrder(node *TreeNode) {
if node == nil {
return
}
printInOrder(node.Left)
fmt.Print(node.Val, " ")
printInOrder(node.Right)
}
func main() {
root := &TreeNode{Val: 2}
root.Left = &TreeNode{Val: 1}
root.Right = &TreeNode{Val: 3}
fmt.Println(isValidBST(root)) // Output: true
fmt.Println(isValidBSTInOrder(root)) // Output: true
printInOrder(root) // Output: 1 2 3
}
kotlin实现
class TreeNode(var `val`: Int) {
var left: TreeNode? = null
var right: TreeNode? = null
}
// 递归验证函数
fun isValidBST(root: TreeNode?): Boolean {
fun validate(node: TreeNode?, low: Long, high: Long): Boolean {
if (node == null) return true
if (node.`val` <= low || node.`val` >= high) return false
return validate(node.left, low, node.`val`.toLong()) && validate(node.right, node.`val`.toLong(), high)
}
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE)
}
// 中序遍历验证函数
fun isValidBSTInorder(root: TreeNode?): Boolean {
var prev: Long = Long.MIN_VALUE
fun inorder(node: TreeNode?): Boolean {
if (node == null) return true
if (!inorder(node.left)) return false
if (node.`val`.toLong() <= prev) return false
prev = node.`val`.toLong()
return inorder(node.right)
}
return inorder(root)
}
// 测试示例
fun main() {
val root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)
println(isValidBST(root)) // 输出: true
println(isValidBSTInorder(root)) // 输出: true
}
