LeetCode Hot100【二叉树-98. 验证二叉搜索树】
题目：98. 验证二叉搜索树代码实现
class Solution {
public:
TreeNode* pre = nullptr;
// 用于记录上一个节点，便于比较当前节点与上一个节点的大小关系
// 验证二叉搜索树的递归函数
bool isValidBST(TreeNode* root) {
if (root == nullptr) return true
;// 空树是有效的二叉搜索树
// 递归检查左子树
bool left = isValidBST(root->left);
// 如果上一个节点的值大于或等于当前节点的值，则不是二叉搜索树
if (pre != nullptr && pre->val >= root->val) return false
;
// 更新上一个节点为当前节点
pre = root;
// 递归检查右子树
bool right = isValidBST(root->right);
// 返回左右子树检查的结果
return left && right;
}
};
执行流程
示例输入
root =
2
/ \
1 3
步骤解析
[*]递归遍历树，起首查抄左子树。
[*]当前节点 root = 2，与 pre = nullptr（没有上一个节点）举行比力，符合条件，更新 pre = 2。
[*]递归查抄右子树。
[*]当前节点 root = 1，与 pre = 2 比力，发现 1 < 2，符合条件，继承查抄右子树。
[*]返回 true
，因为所有节点都符合二叉搜索树的条件。
最终输出：
true
另一个示例输入
root =
5
/ \
1 4
/ \
3 6
步骤解析
[*]递归遍历树，起首查抄左子树。
[*]当前节点 root = 4，与 pre = 1 比力，符合条件，继承查抄右子树。
[*]当前节点 root = 3，与 pre = 4 比力，发现 3 < 4，违反了二叉搜索树的规则，返回 false
。
最终输出：
false
关键思路
[*]中序遍历与前驱节点比力
[*]二叉搜索树（BST）的性子是：对于每个节点，左子树的所有节点值都小于该节点值，右子树的所有节点值都大于该节点值。
[*]通过 中序遍历（左子树 -> 根节点 -> 右子树）可以确保按升序访问树的节点，因此可以通过与前一个节点的值举行比力来验证二叉搜索树的有效性。
[*]通过一个 pre 变量存储上一个访问的节点，每次访问当前节点时，查抄它是否大于前一个节点。
[*]递归深度优先搜索
[*]接纳递归的方式分别查抄左子树和右子树。
[*]先递归查抄左子树，再查抄当前节点与前一个节点的关系，最后递归查抄右子树。
[*]回溯思想
[*]在递归过程中，pre 用于存储上一个节点，在查抄每个节点时更新 pre 的值，确保每个节点都满足 BST 的条件。
时间 & 空间复杂度
操纵时间复杂度空间复杂度递归遍历所有节点O(n)O(h)
[*]时间复杂度： 由于递归遍历树的每个节点一次，时间复杂度为 O(n)，此中 n 是树的节点数。
[*]空间复杂度： 递归调用栈的空间复杂度是 O(h)，此中 h是树的高度。对于均衡树，最坏情况下 h=logn，而对于链状树，空间复杂度为 O(n)。
基础语法解析
1. TreeNode* pre = nullptr;
[*]前驱节点：pre 用来存储上一个遍历的节点，便于在递归中比力当前节点与前一个节点的值。
TreeNode* pre = nullptr;
2. if (pre != nullptr && pre->val >= root->val)
[*]判断当前节点是否正当：通过与前驱节点 pre 的值举行比力，确保当前节点值大于前驱节点值，符合二叉搜索树的要求。
if (pre != nullptr && pre->val >= root->val) return false
; 3. pre = root;
[*]更新前驱节点：在查抄完当前节点后，将 pre 更新为当前节点，以便递归过程中下一次比力。
pre = root;
4. return left && right;
[*]左右子树查抄效果的合并：递归查抄左子树和右子树，最终返回两者的效果，只有当两者都满足二叉搜索树的条件时，当前树才有效。
return left && right;
优化 & 变种
变种 1：非递归版本的中序遍历
通过栈实现非递归版本的中序遍历，逐个查抄每个节点与前驱节点的大小关系。
bool isValidBST(TreeNode* root) { stack<TreeNode*> stack; TreeNode* pre = nullptr;
while (root || !stack.empty()) { while (root) { stack.push(root); root = root->left; } root = stack.top(); stack.pop(); if (pre != nullptr && pre->val >= root->val) return false
; pre = root;
root = root->right; } return true
;} 总结
C++ 语法 / 结构作用TreeNode* pre = nullptr;
用于存储上一个遍历的节点if (pre != nullptr && pre->val >= root->val)判断当前节点与前驱节点的大小关系pre = root;
更新前驱节点时间复杂度： O(n)递归遍历每个节点空间复杂度： O(h)递归栈空间
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]