LeetCode C++ 700. Search in a Binary Search Tree【二叉搜索树】简单
发布日期:2021-07-01 02:52:22
浏览次数:2
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年04月12日 01时07分46秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
pyqt5之俄罗斯方块
2019-05-02
算法排序之归并排序
2019-05-02
算法排序之快速排序
2019-05-02
算法排序之堆排序
2019-05-02
算法排序之计数排序
2019-05-02
算法排序之桶排序
2019-05-02
C++ Template初识函数模板(2.1节,2.2节)
2019-05-02
C++ Template函数模板参数(2.3节)
2019-05-02
C++ Template重载函数模板(2.4节)
2019-05-02
lambda表达式初探
2019-05-02
C++ std::move的使用和使用
2019-05-02
C++ Template类模板(3.1节,3.2节)
2019-05-02
C++11 bind函数
2019-05-02
C++四种类型转换使用示例
2019-05-02
C++ Template类模板的特化(3.3节, 3.4节)
2019-05-02
第05章 函数
2019-05-02
第06章 字符串
2019-05-02
第07章 数据结构
2019-05-02
第08章 输入和输出
2019-05-02
第09章 异常处理
2019-05-02