majianyu
3/3/2019 - 9:02 AM

98. 验证二叉搜索树

  • 递归验证, 设置 min 和 max 值
  • 如果当前节点为nil, return true
  • 如果当前节点小于等于 min 值 , return false
  • 如果当前节点大于等于 max 值, return false
  • 递归左子树,min 值不变,max 值为当前节点
  • 递归右子树, min 值为当前节点, max 值不变

另外一个思路是采用中序遍历,保存last 指针,判断 last 指针是否小于当前值

main.go
content_copyfile_download
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    return isValid(root, -1<<63, 1<<63 - 1)
}
func isValid(root *TreeNode, min, max int) bool {
	if root == nil {
		return true
	}
	if root.Val <= min {
		return false
	}
	if root.Val >= max {
		return false
	}
	return isValid(root.Left, min, root.Val) && isValid(root.Right, root.Val, max)
}
main2.go
content_copyfile_download
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    inorder := inOrder(root)
	for i:=1;i<len(inorder) ;i++ {
		if inorder[i-1] >= inorder[i] {
			return false
		}
	}
	return true
}
func inOrder(root *TreeNode) []int {
	if root == nil {
		return []int{}
	}
	return append(append(inOrder(root.Left), root.Val), inOrder(root.Right)...)
}