检查查找二叉树合法性

问题

如何检验一个二叉树是否是合法的二叉搜索树？

解法

要检验首先要从二叉搜索树的性质下手：树是一个空树，或其满足以下条件：

• 对于任意一个节点，若左子树不为空，则左子树上所有节点的值均小于它的值
• 对于任意一个节点，若右子树不为空，则右子树上所有节点的值均大于它的值

对于空树，直接满足条件；对于非空树，需要递归地遍历树，检查是否满足条件，只有左右子树都满足，才是二叉搜索树。

func isValidBst(root *BTNode) bool {
	return checkBst(root, nil, nil)
}

func checkBst(root, min, max *BTNode) bool {
	if root == nil {
		// 当前节点为空，是二叉搜索树
		return true
	}
	if min != nil && root.Data <= min.Data {
		// 当前节点值小于等于最小值，肯定不是二叉搜索树
		return false
	}
	if max != nil && root.Data >= max.Data {
		// 当前节点值大于等于最小值，肯定不是二叉搜索树
		return false
	}
	// 对于左子树来说，最大值是自己
	// 对于右子树来说，最小值是自己
	// 如果左子树和右子树都是二叉搜索树，则自己就是二叉搜索树
	return checkBst(root.Left, min, root) && checkBst(root.Right, root, max)
}

func main() {
	btree := NewBTree(9)

	btree.Left = &BTNode{
		Data: 4,
		Left: &BTNode{Data: 3, Left: &BTNode{Data: 1}},
		Right: &BTNode{
			Data: 6,
			Left: &BTNode{
				Data: 5,
			},
			Right: &BTNode{
				Data: 7,
			},
		},
	}
	btree.Right = &BTNode{
		Data: 14,
		Left: &BTNode{
			Data: 12,
		},
		Right: &BTNode{
			Data: 15,
		},
	}

	fmt.Println("is valid bst?", isValidBst(btree))

	// 修改一个节点，使其值小于根节点
	btree.Right.Left.Data = 2
	fmt.Println("is valid bst?", isValidBst(btree))
}

输出：

is valid bst? true
is valid bst? false