leetcode--验证二叉搜索树

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

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 
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

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
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38