98. 验证二叉搜索树

题目描述

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

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

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

示例 1：

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

示例 2：

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

提示：

树中节点数目范围在 [1, 10⁴] 内
-2³¹ <= Node.val <= 2³¹ - 1

解法一：递归

 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


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type Result struct {
    isValid bool
    minVal  int
    maxVal  int
}

func isValidBST(root *TreeNode) bool {
    if root == nil {
        return true
    }
    var dfs func(root *TreeNode) *Result
    dfs = func(root *TreeNode) *Result {
        ret := &Result{}
        if root.Left == nil && root.Right == nil {
            ret.isValid, ret.minVal, ret.maxVal = true, root.Val, root.Val
        } else if root.Left == nil {
            // root.Right != nil
            rightRes := dfs(root.Right)
            if rightRes.isValid && rightRes.minVal > root.Val {
                ret.isValid, ret.minVal, ret.maxVal = true, root.Val, rightRes.maxVal
            }
        } else if root.Right == nil {
            // root.Left != nil
            leftRes := dfs(root.Left)
            if leftRes.isValid && leftRes.maxVal < root.Val {
                ret.isValid, ret.minVal, ret.maxVal = true, leftRes.minVal, root.Val
            }
        } else {
            // root.Left != nil && root.Right != nil
            leftRes := dfs(root.Left)
            rightRes := dfs(root.Right)
            if leftRes.isValid && rightRes.isValid && leftRes.maxVal < root.Val && rightRes.minVal > root.Val {
                ret.isValid, ret.minVal, ret.maxVal = true, leftRes.minVal, rightRes.maxVal
            }
        }
        return ret
    }
    res := dfs(root)
    return res.isValid
}