二叉搜索树（Binary Search Tree，BST）是一种二叉树，它或者是一棵空树，或者是具有下列性质的二叉树：
- 若左子树不空，则左子树上所有结点的值均小于它的根结点的值，右子树上所有结点的值均大于根结点的值
- 中序遍历树的每个结点是有序的
验证二叉搜索树
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
| func main() {
ans := isValidBST(&TreeNode{Val: 4, Left: &TreeNode{2, &TreeNode{1, nil, nil}, &TreeNode{3, nil, nil}}})
fmt.Println(ans)
}
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func isValidBST(root *TreeNode) bool {
pre := math.MinInt64
var dfs func(*TreeNode) bool
dfs = func(node *TreeNode) bool {
if node == nil {
return true
}
if !isValidBST(node.Left) {
return false
}
if node.Val <= pre {
return false
}
pre = node.Val
return dfs(node.Right)
}
return dfs(root)
}
|
