Joyce' Blog
0%

validate-binary-search-tree

发表于 更新于

题目描述

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

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

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

题解

这不就，递归吗？有快一点的方法吗……

注意不能相等哦。还要注意左边的最大值小于右边的最小值。

第一版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int getMax(TreeNode* root)
{
	if (!root->right)
		return root->val;
	return getMax(root->right);
}
int getMin(TreeNode* root)
{
	if (!root->left)
		return root->val;
	return getMax(root->left);
}
bool isValidBST(TreeNode* root) {
	if (root == NULL || (root->left == NULL && root->right == NULL))
		return true;
	if ((root->left&&root->val<=getMax(root->left)) || (root->right&&root->val>=getMin(root->right)))
		return false;
	return isValidBST(root->left) && isValidBST(root->right);
}

执行用时 :24 ms, 在所有 C++ 提交中击败了27.46%的用户

内存消耗 :20.1 MB, 在所有 C++ 提交中击败了100.00%的用户

做了很多重复的工作，所以时间效率很低。再改改。

我真是傻逼。中序遍历啊！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool midtravel(TreeNode* root,stack<int>& s)
{
	if (root == NULL)
		return true;
	if (root->left)
		if(!midtravel(root->left,s))return false;
	if (!s.empty() && s.top() >= root->val)return false;
	s.push(root->val);
	if (root->right)
		if (!midtravel(root->right, s))return false;
	return true;
}
bool isValidBST(TreeNode* root) {
	if (root == NULL || (root->left == NULL && root->right == NULL))
		return true;
	stack<int> s;
	return midtravel(root, s);
}

执行用时 :16 ms, 在所有 C++ 提交中击败了76.37%的用户

内存消耗 :20.3 MB, 在所有 C++ 提交中击败了97.25%的用户

再来个下酒菜

1
2
3
4
5
6
7
8
9
10
11
12
bool isSameTree(TreeNode* p, TreeNode* q) {
	if (p == NULL)
	{
		if (q == NULL)
			return true;
		else
			return false;
	}
	if (q == NULL)return false;
	if (p->val != q->val)return false;
	return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}