98-ValidataBinarySearchTree

验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

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

输入:
    2
   / \
  1   3
输出: true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1

// isValidBSTLeft 左边返回最大值
// 判断思路返回字数的左最大和右再和跟比较判断条件比较复杂
// 收集意见的方式需要大量的记录和调查比较
func isValidBSTRe (root * TreeNode) (bool,int,int){
	// 为假的情况先返回
	// 左边大于返回false
	var min,max,leftMax,rightMin int
	var left,right ,leftNil,rightNil bool
	if root.Left != nil && root.Left.Val > root.Val{
		return false,0,0
	}
	//右边小返回false
	if root.Right != nil && root.Right.Val < root.Val{
		return false,0,0
	}
	if root.Right == nil && root.Left ==nil{
		return true,root.Val,root.Val
	}
	// 判断左情况
	if root.Left == nil {
		min = root.Val
		left = true
		leftNil = true

	}else{
		left ,min,leftMax = isValidBSTRe(root.Left)
	}
	if root.Right == nil {
		max = root.Val
		rightNil = true
		right = true
	} else {
		right,rightMin,max = isValidBSTRe(root.Right)
	}
	if left && right && (leftMax < root.Val || leftNil) && (rightMin > root.Val || rightNil ){
		return true,min,max
	}
	return false,0,0
}

思路2

// _isValidBST从上到到下限制子树约束条件，简单方便
// 立规矩的方式，你就按照我的范围搞，符合条件你愿意是啥是啥！
func _isValidBST(root *TreeNode, min int, max int) bool {
	if root == nil {
		return true
	}
	if min >= root.Val || root.Val >= max {
		return false
	}

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

}

总结

可以看到两个想法实际上本质都是递归但是在处理子树最大和最小值时候是完全两种思路。
方法1:收集子树的反馈（做调查），根节点比较民主，你们报上你们的范围，我看看我跟你们匹配不不匹配我不称职好我下台。跟的父亲发现自己选的下级下台了，完了我一手提拔的下台了我也下台吧。比较民主但是实现复杂，需要记录各种状态，但是可以保存每一步子树的情况后续可以进一步扩展。
方法2:给每个子树限定范围（立规矩），跟节点“老子就这样，你们按老子标准走，不符合的滚，老子上报下是这帮儿子不行连累了我不行”。方法简单，每次只需要把根节点的值最为范围立规范。依次往下迭代就行。但是没有记录下面的状态题目变更后可能不再适用。