LeetCode C++ 面试题 04.05. Legal Binary Search Tree LCCI【Binary Search Tree/DFS】中等
发布日期:2021-07-01 02:57:12
浏览次数:4
分类:技术文章
本文共 1341 字,大约阅读时间需要 4 分钟。
Implement a function to check if a binary tree is a binary search tree.
Example 1:
Input: 2 / \ 1 3Output: true
Example 2:
Input: 5 / \ 1 4 / \ 3 6Output: falseExplanation: Input: [5,1,4,null,null,3,6]. the value of root node is 5, but its right child has value 4.
题意:实现一个函数,检查一棵二叉树是否为二叉搜索树。
解法1 迭代中序遍历
class Solution { public: bool isValidBST(TreeNode* root) { if (root == nullptr) return true; TreeNode *prev = nullptr; stackst; while (root || !st.empty()) { while (root) { st.push(root); root = root->left; } root = st.top(); st.pop(); if (prev && prev->val >= root->val) return false; //注意:直接前驱的值必须 <直接后继的值 prev="root;" root="root-"> right; } return true; }}; 直接后继的值>
执行效率如下:
执行用时:20 ms, 在所有 C++ 提交中击败了64.43% 的用户内存消耗:21.7 MB, 在所有 C++ 提交中击败了9.92% 的用户
解法2 递归中序遍历
class Solution { public: TreeNode *prev = nullptr; bool isValidBST(TreeNode* root) { if (root == nullptr) return true; if (!isValidBST(root->left)) return false; if (prev && prev->val >= root->val) return false; prev = root; if (!isValidBST(root->right)) return false; return true; }};
执行效率如下:
执行用时:16 ms, 在所有 C++ 提交中击败了89.01% 的用户内存消耗:21.4 MB, 在所有 C++ 提交中击败了39.61% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/110161749 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月19日 01时13分34秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
实时开发框架Meteor API解读系列<五>Session
2019-05-03
实时开发框架Meteor API解读系列<六> DDP
2019-05-03
实时开发框架Meteor 实际应用系列<一>---文件的上传和下载[补充]
2019-05-03
实时开发框架Meteor API解读系列<七> Collection --01
2019-05-03
实时开发框架Meteor API解读系列<八> Timers
2019-05-03
ubuntu sublime无法输入中文问题
2019-05-03
启用fcitx-qimpanel面板程序
2019-05-03
浅谈Q的基本实现
2019-05-03
// 根据图片url获取图片尺寸
2019-05-03
iOS APP在App Store上的主标题长度增加、显示副标题、安装后只显示主标题
2019-05-03
iOS UIKeyboardType(键盘类型)~图解
2019-05-03
iOS 将ImageView上的控件合成一张Image
2019-05-03
iOS-带图片的二维码的生成(QRCode)
2019-05-03
iOS,图片的填充模式
2019-05-03
iOS 监听UIScrollView滚动停止
2019-05-03
ios FMDB 简单使用
2019-05-03
iOSUIPickerView使用
2019-05-03
iOS开发 获取手机型号
2019-05-03
获取iOS设备UUID
2019-05-03
iOS 苹果开发者账号续费-图文教程
2019-05-03