C++递归实现验证⼆叉搜索树
📟作者主页:慢热的陕西人
🌴专栏链接:力扣刷题日记
📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言
题目链接
98. 验证二叉搜索树 - 力扣(LeetCode)
题目描述
给你⼀个⼆叉树的根节点root,判断其是否是⼀个有效的⼆叉搜索树。
有效⼆叉搜索树定义如下:
- 节点的左⼦树只包含⼩于当前节点的数。
- 节点的右⼦树只包含⼤于当前节点的数。
- 所有左⼦树和右⼦树⾃⾝必须也是⼆叉搜索树。
解题思路
利用中序遍历;
后序遍历按照左⼦树、根节点、右⼦树的顺序遍历⼆叉树的所有节点,通常⽤于⼆叉搜索树相关题⽬。
算法思路:
如果⼀棵树是⼆叉搜索树,那么它的中序遍历的结果⼀定是⼀个严格递增的序列。
因此,我们可以初始化⼀个⽆穷⼩的全区变量,⽤来记录中序遍历过程中的前驱结点。那么就可以在
中序遍历的过程中,先判断是否和前驱结点构成递增序列,然后修改前驱结点为当前结点,传⼊下⼀
层的递归中。算法流程:
初始化⼀个全局的变量**
prev
,⽤来记录中序遍历过程中的前驱结点的val
**;中序遍历的递归函数中 :
a.设置递归出⼝:
root==nullptr
的时候,返回true
;b. 先递归判断左⼦树是否是⼆叉搜索树,⽤**
retleft
**标记;c.然后判断当前结点是否满⾜⼆叉搜索树的性质,⽤**
retcur
**标记:
- 如果当前结点的**
val
⼤于prev
,说明满⾜条件,retcur
改为true
**;- 如果当前结点的val⼩于等于**
prev
,说明不满⾜条件,retcur
改为false
**;d.最后递归判断右⼦树是否是⼆叉搜索树,⽤**
retright
**标记;文章来源:https://www.toymoban.com/news/detail-734510.html
- 只有当**
retleft、retcur和retright
都是true
的时候,才返回true
**。
C++算法代码:
class Solution { long prev = LONG_MIN; public: bool isValidBST(TreeNode* root) { if(root == nullptr) return true; bool left = isValidBST(root->left); // 剪枝 if(left == false) return false; bool cur = false; if(root->val > prev) cur = true; // 剪枝 if(cur == false) return false; prev = root->val; bool right = isValidBST(root->right); return left && right && cur; } };
总结
我们利用了剪枝的优化方式,提高了代码的运行效率,同时采用了全局变量
prev
来标记前序节点,也提高了程序的运行效率,并且将我们实现的过程简单化。文章来源地址https://www.toymoban.com/news/detail-734510.html
到了这里,关于C++递归实现验证⼆叉搜索树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!