LeetCode C++ 面试题 04.06. Successor LCCI【Binary Search Tree/DFS】中等
发布日期:2021-07-01 02:57:13
浏览次数:2
分类:技术文章
本文共 2120 字,大约阅读时间需要 7 分钟。
Write an algorithm to find the “next” node (i.e., in-order successor) of a given node in a binary search tree.
Return null
if there’s no “next” node for the given node.
Example 1:
Input: root = [2,1,3], p = 1 2 / \1 3Output: 2
Example 2:
Input: root = [5,3,6,2,4,null,null,1], p = 6 5 / \ 3 6 / \ 2 4 / 1Output: null
题意:找出二叉搜索树中指定节点的中序直接后继结点。如果指定节点没有对应的直接后继,则返回 null
。
解法1 迭代中序遍历
迭代中序遍历,首先找到 p
,然后取出 p
的直接后继结点。此处为了同时得到当前结点 cur
和其对应的直接后继 succ
,使用右根左的遍历顺序:
class Solution { public: TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) { TreeNode *succ = nullptr; stackst; while (root || !st.empty()) { while (root) { st.push(root); root = root->right; } root = st.top(); st.pop(); if (root == p) return succ; //当前结点==p,后继结点为succ succ = root; root = root->left; } return succ; }};
执行效率如下:
执行用时:40 ms, 在所有 C++ 提交中击败了77.48% 的用户内存消耗:22.9 MB, 在所有 C++ 提交中击败了20.82% 的用户
解法2 递归中序遍历
使用右根左的遍历顺序:
class Solution { private: TreeNode *succ = nullptr, *ans = nullptr; void dfs(TreeNode* root, TreeNode* p) { if (root == nullptr) return; dfs(root->right, p); if (root == p) ans = succ; succ = root; dfs(root->left, p); }public: TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) { if (root == nullptr) return nullptr; dfs(root, p); return ans; }};
效率如下, O ( n ) O(n) O(n) 时间:
执行用时:40 ms, 在所有 C++ 提交中击败了77.48% 的用户内存消耗:22.9 MB, 在所有 C++ 提交中击败了25.60% 的用户
解法3 利用二叉搜索树特性
class Solution { public: TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) { if (root == nullptr) return nullptr; //当前节点值<=目标节点值,则目标节点的后继必然存在于右子树中 if (p->val >= root->val) return inorderSuccessor(root->right, p); //否则结果可能是当前节点,或者在当前节点的左子树中 TreeNode *succ = inorderSuccessor(root->left, p); return succ ? succ : root; //如果左子树中存在后继,则返回;否则返回当前节点 }};
执行效率如下:
执行用时:44 ms, 在所有 C++ 提交中击败了53.91% 的用户内存消耗:23 MB, 在所有 C++ 提交中击败了19.96% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/110207896 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
逛到本站,mark一下
[***.202.152.39]2024年04月14日 00时55分09秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
来吧,用设计模式来干掉 if-else
2019-05-02
为什么 Redis 要比 Memcached 更火?
2019-05-02
涨姿势:为啥MySQL官方不推荐使用uuid或者雪花id作为主键?
2019-05-02
一个小小的签到功能,到底用MySQL还是Redis?
2019-05-02
36岁退休!阿里 P8 六年实现“财务自由”,裸辞环游世界!
2019-05-02
QQ号终于能修改了?
2019-05-02
1.3 万亿条数据查询,如何做到毫秒级响应?
2019-05-02
高赞回答:为什么高级程序员不必担心自己的技术过时?
2019-05-02
支持 Dubbo 接口文档生成的工具
2019-05-02
SpringBoot集成WebSocket,实现后台向前端推送信息
2019-05-02
基于SpringBoot实现单点登录系统
2019-05-02
优秀程序员早就学会用“状态模式”代替if-else了
2019-05-02
使用基于 SpringMVC 的透明 RPC 开发微服务
2019-05-02
写“好”代码的十九条准则
2019-05-02
推荐几款 Redis 可视化工具
2019-05-02
送60本书!!
2019-05-02
丁威: 优秀程序员必备技能之如何高效阅读源码(二更)
2019-05-02
基于 SpringBoot,来实现MySQL读写分离技术
2019-05-02
程序员该如何把 Windows 系统打造的跟 Mac 一样牛逼?
2019-05-02
SpringBoot+Vue 完整的外卖系统,手机端和后台管理,可以玩一下!
2019-05-02