008.验证二叉搜索树

• 98.验证二叉搜索树
  • 中序遍历
  • 递归

验证二叉搜索树 - 递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
	_, _, is := process(root)
	return is
}
 
func process(root *TreeNode) (minn, maxx *int, is bool) {
	if root == nil {
		is = true
		return
	}
 
	lMin, lMax, lIs := process(root.Left)
	if !lIs || lMax != nil && *lMax >= root.Val {
		is = false
		return
	}
 
	rMin, rMax, rIs := process(root.Right)
	if !rIs || rMin != nil && *rMin <= root.Val {
		is = false
		return
	}
 
	if lMin == nil {
		lMin = &root.Val
	}
	if rMax == nil {
		rMax = &root.Val
	}
 
	return lMin, rMax, true
}