98. 验证二叉搜索树

mid

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

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

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

递归

需要提供当前最小值和最大值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
// 递归
func isValidBST(root *TreeNode) bool {
	var help func(root *TreeNode, minVal, maxVal int) bool

	help = func(root *TreeNode, minVal, maxVal int) bool {
		if root == nil {
			return true
		}

		if root.Val <= minVal || root.Val >= maxVal {
			return false
		}

		return help(root.Left, minVal, root.Val) && help(root.Right, root.Val, maxVal)
	}

	return help(root, math.MinInt64, math.MaxInt64)
}

栈 + 中序遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func isValidBST(root *TreeNode) bool {
	stack := make([]*TreeNode, 0)
	lastNodeVal := math.MinInt64
	curNode := root

	for len(stack) != 0 || curNode != nil {
		if curNode != nil {
			stack = append(stack, curNode)
			curNode = curNode.Left
		} else {
			curNode = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			// 跟中序遍历的上一个节点值比较
			if curNode.Val <= lastNodeVal {
				return false
			}
			lastNodeVal = curNode.Val
			curNode = curNode.Right
		}
	}
	return true
}