leetcode 98. 验证二叉搜索树

题解

暴力递归,直接判断是否符合二叉搜索树的标准,左子树上所有结点的值均小于它的根结点的值,右子树上所有结点的值均大于它的根结点的值

示例代码(go)

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
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isValidBST(root *TreeNode) bool {
if root == nil {
return true
}
if !isValidLeft(root.Left, root.Val) {
return false
}
if !isValidRight(root.Right, root.Val) {
return false
}
return isValidBST(root.Left) && isValidBST(root.Right)
}

func isValidLeft(root *TreeNode, val int) bool {
if root == nil {
return true
}
if root.Val >= val {
return false
}
return isValidLeft(root.Left, val) && isValidLeft(root.Right, val)
}

func isValidRight(root *TreeNode, val int) bool {
if root == nil {
return true
}
if root.Val <= val {
return false
}
return isValidRight(root.Left, val) && isValidRight(root.Right, val)
}