leetcode 98. 验证二叉搜索树

题目描述

给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:

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

示例 1:

输入:
    2
   / \
  1   3
输出: true
示例 2:
输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ,但是其右子节点值为 4 。

题解

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

示例代码(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)
}