手撸二叉树之二叉搜索树中的搜索
发布于: 2 小时前
Hello, 大家好，今天是我参加 8 月更文的第 9 天，今天给大家带来的关于二叉树相关的算法题是二叉搜索树中的搜索，正文如下：
题目：
给定二叉搜索树（BST）的根节点和一个值。 你需要在 BST 中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
例如：
你应该返回如下子树:
在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。
解题思路
递归实现非常简单：
如果根节点为空 root == null 或者根节点的值等于搜索值 val == root.val，返回根节点。
如果 val < root.val，进入根节点的左子树查找 searchBST(root.left, val)。
如果 val > root.val，进入根节点的右子树查找 searchBST(root.right, val)。
返回根节点。
代码实现
复制代码
最后
复杂度分析
时间复杂度：O(h)，其中 h 是树高。平均时间复杂度为 O(logN)，最坏时间复杂度为 O(N)。
空间复杂度：O(h)，递归栈的深度为 h。平均情况下深度为 O(logN)，最坏情况下深度为 O(N)。
版权声明: 本文为 InfoQ 作者【HelloWorld杰少】的原创文章。
原文链接:【http://xie.infoq.cn/article/37e61bc456d7346bfca86b706】。文章转载请联系作者。
佛系编码 2019.05.13 加入
红鲤鱼与绿鲤鱼与驴。
评论