98. Validate Binary Search Tree

判断一棵二叉搜索树是否有效。有效是指每个节点的值大于左节点，小于右节点（如果有对应节点的话），且它的左节点和右节点也满足这种条件。

思路：递归检测每个节点，一个节点的左子树的节点的值都在最小值和跟节点之间，右子数的所有节点的值都在跟节点和最大值之间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        # 6 star, 多练习
        import sys
        return self.is_valid(-sys.maxsize, sys.maxsize, root)

    def is_valid(self, min, max, node):
        # 注意引入了上限和下限两个变量来比较
        if not node:
            return True
        if node.val <= min or node.val >= max:
            return False
        return self.is_valid(min, node.val, node.left) and self.is_valid(node.val, max, node.right)

Go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func isValidBST(root *TreeNode) bool {
	if root == nil {return true}
	return helper(root, math.MinInt64, math.MaxInt64)

}

func helper(node *TreeNode, min int, max int) bool {
	if node.Val <= min || node.Val >= max {
		return false
	}
	left, right := true, true
	if node.Left != nil {
		left = helper(node.Left, min, node.Val)
	}
	if node.Right != nil {
		right = helper(node.Right, node.Val, max)
	}
	return left && right
}