package validatebinarysearchtree

import . "gitee.com/dllearn/geektime-algorithm-learn/structures"

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
	const MaxUint = ^uint(0)
	// const MinUint = 0
	const MaxInt = int(MaxUint >> 1)
	const MinInt = -MaxInt - 1
	return check(root, MinInt, MaxInt)
}

func check(node *TreeNode, left, right int) bool {
	if node == nil {
		return true
	}
	if node.Val < left || node.Val > right {
		return false
	}
	return check(node.Left, left, node.Val-1) && check(node.Right, node.Val+1, right)
}