【LeetCode】二叉搜索树中的搜索 Java 题解
题目描述
给定二叉搜索树(BST)的根节点和一个值。 你需要在 BST 中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。
复制代码
思路分析
今天的算法每日一题是二叉搜索树查找问题。什么是二叉搜索树呢?
二叉搜索树(Binary Search Tree 或者是一棵空树,或者是具有下列性质的二叉树:
若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
它的左、右子树也分别为二叉排序树。
利用二叉搜索树以上的性质,我们就可以快速查找题目节点子树。实现代码如下:
通过代码
复制代码
总结
递归算法的时间复杂度是 O(log n),空间复杂度是 O(log n)
二叉搜索树是一种经典的数据结构,它既有链表的快速插入与删除操作的特点,又有数组快速查找的优势;所以应用十分广泛,例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。我们要掌握好这种数据结构。
坚持算法每日一题,加油!
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/60b339670cc89252e026306e5】。文章转载请联系作者。
评论