Day111 | 灵神 | 二叉树 | 验证二叉搜索树
98.验证二叉搜索树
方法一：前序遍历
递归函数传入合法的左右边界，只有当前结点是合法的边界，才是二叉搜索树，否则就返回false
对于左子树就传入当前结点的左边界，和当前结点的值作为右边界，从而验证左子树是一颗二叉搜索树
对于右子树就传入当前结点的右边界，和当前结点的值作为左边界，从而验证右子树是一颗二叉搜索树
只有当前结点符合条件并且左右子树也都是二叉搜索树才会返回true
灵神前序遍历代码：
class Solution {
public:
bool isValidBST(TreeNode* root, long long left = LLONG_MIN, long long right = LLONG_MAX) {
if (root == nullptr) {
return true;
}
long long x = root->val;
return left < x && x < right &&
isValidBST(root->left, left, x) &&
isValidBST(root->right, x, right);
}
};
复杂度分析
- 时间复杂度：O(n)，其中 n 为二叉搜索树的节点个数。
- 空间复杂度：O(n)。最坏情况下，二叉搜索树退化成一条链（注意题目没有保证它是平衡树），因此递归需要 O(n) 的栈空间。
方法二：中序遍历
二叉树搜索树的中序遍历是一个有序序列，记录前一个值，如果当前结点的值比前一个值小就是false
class Solution {
public:
TreeNode *pre=nullptr;
bool tra(TreeNode *t)
{
if(t==nullptr)
return true;
bool l=tra(t->left);
if(pre!=nullptr)
if(t->val<=pre->val)
return false;
pre=t;
bool r=tra(t->right);
return l&&r;
}
bool isValidBST(TreeNode* root) {
return tra(root);
}
};
灵神中序遍历代码：
class Solution {
long long pre = LLONG_MIN;
public:
bool isValidBST(TreeNode* root) {
if (root == nullptr) {
return true;
}
if (!isValidBST(root->left) || root->val <= pre) {
return false;
}
pre = root->val;
return isValidBST(root->right);
}
};
复杂度分析
- 时间复杂度：O(n)，其中 n 为二叉搜索树的节点个数。
- 空间复杂度：O(n)。最坏情况下，二叉搜索树退化成一条链（注意题目没有保证它是平衡树），因此递归需要 O(n) 的栈空间。
方法三：后序遍历
灵神后序遍历代码：
class Solution {
pair<long long, long long> dfs(TreeNode* node) {
if (node == nullptr) {
return {LLONG_MAX, LLONG_MIN};
}
auto[l_min, l_max] = dfs(node->left);
auto[r_min, r_max] = dfs(node->right);
long long x = node->val;
// 也可以在递归完左子树之后立刻判断，如果发现不是二叉搜索树，就不用递归右子树了
if (x <= l_max || x >= r_min) {
return {LLONG_MIN, LLONG_MAX};
}
return {min(l_min, x), max(r_max, x)};
}
public:
bool isValidBST(TreeNode* root) {
return dfs(root).second != LLONG_MAX;
}
};
复杂度分析
- 时间复杂度：O(n)，其中 n 为二叉搜索树的节点个数。
- 空间复杂度：O(n)。最坏情况下，二叉搜索树退化成一条链（注意题目没有保证它是平衡树），因此递归需要 O(n) 的栈空间。
灵神点评
- 前序遍历在某些数据下不需要递归到叶子节点就能返回（比如根节点左儿子的值大于根节点的值，左儿子就不会继续往下递归了），而中序遍历和后序遍历至少要递归到一个叶子节点。从这个角度上来说，前序遍历是最快的。
- 中序遍历很好地利用了二叉搜索树的性质，使用到的变量最少。
- 后序遍历的思想是最通用的，即自底向上计算子问题的过程。想要学好动态规划的话，请务必掌握自底向上的思想。