LeetCode-98.验证二叉搜索树

二叉树#

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

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

节点的左子树只包含 严格小于 当前节点的数。

节点的右子树只包含 严格大于 当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

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

示例 2：

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

自己的解法

思路：从题目中可以看到二叉搜索树定义，

其中isValidBST的递归，能够保证所有左子树和右子树自身必须也是二叉搜索树。
所以，我们只需要保证，本身的节点的大小能够比左边最大的大，比右边最小的小即可

我就是再来个递归获取最大和最小值

1
/**
2
 * Definition for a binary tree node.
3
 * type TreeNode struct {
4
 *     Val int
5
 *     Left *TreeNode
6
 *     Right *TreeNode
7
 * }
8
 */
9
func isValidBST(root *TreeNode) bool {
10
    if root == nil {
11
        return true
12
    }
13

14
    left := isValidBST(root.Left)
15
    leftmax := findmax(root.Left)
16

17
    right := isValidBST(root.Right)
18
    rightmin := findmin(root.Right)
19

20
    if leftmax != nil && rightmin != nil {
21
        if leftmax.Val >= root.Val || root.Val >= rightmin.Val {
22
            return false
23
        }
24
    }else if leftmax == nil && rightmin != nil {
25
        if root.Val >= rightmin.Val {
26
            return false
27
        }
28
    }else if leftmax != nil && rightmin == nil {
29
        if root.Val <= leftmax.Val {
30
            return false
31
        }
32
    }
33

34
    return left && right
35
}
36

37
func findmax(root *TreeNode) *TreeNode {
38
    if root == nil {
39
        return nil
40
    }
41

42
    if root.Right == nil {
43
        return root
44
    }
45

46
    return findmax(root.Right)
47
}
48

49
func findmin(root *TreeNode) *TreeNode {
50
    if root == nil {
51
        return nil
52
    }
53

54
    if root.Left == nil {
55
        return root
56
    }
57

58
    return findmin(root.Left)
59
}

设定上下边界法

思路：给我的方法优化了一下

1
func isValidBST(root *TreeNode) bool {
2
    return validate(root, math.MinInt, math.MaxInt)
3
}
4

5
func validate(node *TreeNode, min, max int) bool {
6
    if node == nil {
7
        return true
8
    }
9

10
    if node.Val <= min || node.Val >= max {
11
        return false
12
    }
13

14
    leftValid := validate(node.Left, min, node.Val)
15

16
    rightValid := validate(node.Right, node.Val, max)
17

18
    return leftValid && rightValid
19
}

中序遍历法

思路：二叉搜索树进行中序遍历，得到的结果一定是一个「严格递增」的有序序列

所以只需要进行中序遍历，再比较大小即可

1
func isValidBST(root *TreeNode) bool {
2
    preVal := math.MinInt
3

4
    var inorder func(*TreeNode) bool
5
    inorder = func(node *TreeNode) bool {
6
        if node == nil {
7
            return true
8
        }
9

10
        leftValid := inorder(node.Left)
11

12
        if node.Val <= preVal {
13
            return false
14
        }
15
        preVal = node.Val
16

17
        rightValid := inorder(node.Right)
18

19
        return leftValid && rightValid
20
    }
21

22
    return inorder(root)
23
}