LeetCode C++ 700. Search in a Binary Search Tree【二叉搜索树】简单
发布日期:2021-07-01 02:52:22
浏览次数:3
分类:技术文章
本文共 1390 字,大约阅读时间需要 4 分钟。
Given the root node of a binary search tree BST
and a value. You need to find the node in the BST
that the node’s value equals the given value. Return the subtree rooted with that node. If such node doesn’t exist, you should return NULL
.
For example,
Given the tree: 4 / \ 2 7 / \ 1 3And the value to search: 2
You should return this subtree:
2 / \ 1 3
In the example above, if we want to search the value 5
, since there is no node with value 5
, we should return NULL
.
Note that an empty tree is represented by NULL
, therefore you would see the expected output (serialized tree format) as []
, not null
.
题意:给定二叉搜索树的根节点和一个值。 需要在BST中找到节点值等于给定值的节点,返回以该节点为根的子树。 如果节点不存在,则返回 NULL
。
思路1:递归实现
class Solution { public: TreeNode* searchBST(TreeNode* root, int val) { if (root == nullptr || root->val == val) return root; return val < root->val ? searchBST(root->left, val) : searchBST(root->right, val); }};
效率如下:
执行用时:64 ms, 在所有 C++ 提交中击败了95.52% 的用户内存消耗:34 MB, 在所有 C++ 提交中击败了58.19% 的用户
思路2:迭代实现
class Solution { public: TreeNode* searchBST(TreeNode* root, int val) { while (true) { if (root == nullptr || root->val == val) return root; root = val < root->val ? root->left : root->right; } }};
效率如下:
执行用时:76 ms, 在所有 C++ 提交中击败了55.36% 的用户内存消耗:34 MB, 在所有 C++ 提交中击败了54.38% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/108813323 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2024年04月16日 19时56分01秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
使用swig为python添加c扩展总结
2021-07-05
禅道程序员的10条原则
2021-07-05
python开发总结五
2021-07-05
简单的搭建一个高并发低时延系统
2021-07-05
APUE学习笔记-文件IO
2021-07-05
JDBC
2021-07-05
JDBC
2021-07-05
CMS
2021-07-05
JSP数据交互(一)
2021-07-05
JSP数据交互(二)
2021-07-05
6月9号 数据交互
2021-07-05
jsp数据交互
2021-07-05
EL、JSTL、servlet
2021-07-05
live555学习笔记【6】---客户端(一)
2021-07-05
live555学习笔记【7】---客户端(二)
2021-07-05
2 QCreator调试并查看源码
2021-07-05
3 Qt Creator 添加自定义注释
2021-07-05
4 Qt 之 pro 配置多个子工程/子模块
2021-07-05
5 Qt之Meta-Object 系统
2021-07-05
6 Qt 之属性系统
2021-07-05