题目描述
给定一棵二叉树,判断它是否是一棵合法的二叉搜索树(BST)。
二叉搜索树需要满足如下条件:
- 左子树的所有节点的值都小于当前节点的值;
- 右子树的所有节点的值都大于当前节点的值;
- 左子树和右子树都必须是合法的二叉搜索树;
样例1
输入:
2
/ \
1 3
输出:true
样例2
输入:
5
/ \
1 4
/ \
3 6
输出:false
解释:输入是 5,1,4,null,null,3,6]. 根节点的值是5,
但其右儿子的值是4。
算法
(深度优先遍历) O(n)
深度优先遍历整棵子树。
遍历时,需要向上传递当前子树中的最小值和最大值,这里可以用C++中的引用来专递。
对于当前节点,我们先遍历它的左子树,判断左子树是否合法,同时判断左子树的最大值是否小于当前节点的值;然后遍历右子树,判断右子树是否合法,同时判断右子树的最小值是否大于当前节点的值。
如果条件均满足,说明以当前节点为根的子树是一棵合法的二叉搜索树,返回true。
时间复杂度分析:树中每个节点仅被遍历一遍,所以时间复杂度是 O(n)。
C++ 代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) :
val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode* root) {
if (!root) return true;
int maxv, minv;
return dfs(root, maxv, minv);
}
bool dfs(TreeNode* root, int &maxv, int &minv)
{
maxv = minv = root->val;
if (root->left)
{
int nowMaxv, nowMinv;
if (!dfs(root->left, nowMaxv, nowMinv))
return false;
if (nowMaxv >= root->val)
return false;
maxv = max(maxv, nowMaxv);
minv = min(minv, nowMinv);
}
if (root->right)
{
int nowMaxv, nowMinv;
if (!dfs(root->right, nowMaxv, nowMinv))
return false;
if (nowMinv <= root->val)
return false;
maxv = max(maxv, nowMaxv);
minv = min(minv, nowMinv);
}
return true;
}
};
按照定义来做也太牛了,越看越觉得这个dfs用的真牛
class Solution { public: bool isValidBST(TreeNode* root) { return bfs(root, LONG_MIN, LONG_MAX); } bool bfs(TreeNode* root, long long min, long long max) { if (!root) return true; if (root->val <= min || root->val >= max) return false; //递归遍历左右子树,并且左右儿子的取值范围也会不断更新,缩小取值范围 return bfs(root->left, min, root->val) && bfs(root->right, root->val, max); } };
请问为什么用int无法AC,而y总的可以?
因为这里的max和min是开区间,所以取INT边界的时候会出问题,改成闭区间就可以了:
class Solution { public: bool isValidBST(TreeNode* root) { return dfs(root, INT_MIN, INT_MAX); } bool dfs(TreeNode* root, int min, int max) { if(!root) return true; if(root->val < min || root->val > max) return false; if(root->left && (root->val == INT_MIN || !dfs(root->left, min, root->val-1))) return false; if(root->right && (root->val == INT_MAX || !dfs(root->right, root->val+1, max))) return false; return true; } };
还有一个问题,就是当发现某一个子树不合理以后,可不可以马上终止函数的运行呢,就是不要再进行其他无谓的搜索了,但感觉用递归写的时候,不知道要怎么样做诶
这里的代码就是在遇到不合理的时候直接返回了吧,
if (!dfs(root->left, nowMaxv, nowMinv)) return false;
你说的是尾递归吧
我自己写的时候,递归每次只向上传递当前节点为根的子树里的最大值,应该也是可以的, 不需要同时记录左右节点的最大值,是这样的吗?
这题应该用中旬遍历是递增序列的求解。
对对,这个y总也在讲课的时候说了
对滴,也是可以的。
树为空时候也是搜索树吗
是滴