leetcode 98 验证二叉搜索树

题目

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

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

节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例

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

解析

优先使用迭代法迭代法的中序遍历，去抄下中序的代码：
注意为什么要选择中序遍历，因为二叉搜索树的中序是一个递增数组

/**
 * 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
    }
    stack := list.New()
    cur := root
    var pre *TreeNode //保存上一个指针
    for cur != nil || stack.Len() > 0 {
        if cur != nil {
            stack.PushBack(cur)
            cur = cur.Left
        } else {
            cur = stack.Remove(stack.Back()).(*TreeNode)
            if pre != nil && cur.Val <= pre.Val {
                return false
            }
            pre = cur
            cur = cur.Right
        }
    }
    return 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

使用递归法的话，得先定义最大值和最小值（int64），每次递归的话，判断子树中所有节点的值是否都在 (l,r) 的范围内（注意是开区间）；同时，在递归调用左子树时，我们需要把上界改为 root.val，递归右子树同理。

/**
 * 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
    }
    min := math.MinInt64
    max := math.MaxInt64
    res := check(root, int64(min), int64(max))
    return res
}

func check(node *TreeNode, min, max int64) bool {
    if node == nil {
        return true
    }
    if min >= int64(node.Val) || max <= int64(node.Val) {
        return false
    }
    res := check(node.Left, min, int64(node.Val)) && check(node.Right, int64(node.Val), max)
    return res
}
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