98.M 验证二叉搜索树

Problem: 98. 验证二叉搜索树

思路

思路1：递归。如果当前节点的值满足要求，而且左右子树也都是二叉搜索树，那么整棵树就是二叉搜索树。

思路2：中序遍历。利用二叉搜索树中序遍历的值一定是递增的特点。

Code

代码1：

func isValidBST(root *TreeNode) bool {
	return helper(root, math.MinInt, math.MaxInt)
}

func helper(root *TreeNode, min int, max int) bool {
	if root == nil {
		return true
	}

	if root.Val <= min || root.Val >= max {
		return false
	}

	return helper(root.Left, min, root.Val) && helper(root.Right, root.Val, max)
}

代码2：

func isValidBST(root *TreeNode) bool {
	var stack []*TreeNode
	var last = math.MinInt
	for root != nil || len(stack) > 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}

		root = stack[len(stack)-1]
		stack = stack[0 : len(stack)-1]
		if root.Val <= last {
			return false
		}
		last = root.Val
		root = root.Right
	}

	return true
}