Binary Search Tree 以及一道 LeetCode 题目
一道LeetCode题目
今天刷一道LeetCode的题目,要求是这样的:
Given a binary search tree and the lowest and highest boundaries as
L
andR
, trim the tree so that all its elements lies in [L
,R
] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.
由于对于 Binary search tree 不理解,所以绕了点弯路,要解这道题,必须理解什么是 binary search tree。我们来看一下定义:
A binary search tree is a rooted binary tree, whose internal nodes each store a key (and optionally, an associated value) and each have two distinguished sub-trees, commonly denoted left and right. The tree additionally satisfies the binary search property, which states that the key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree.[1]:287 (The leaves (final nodes) of the tree contain no key and have no structure to distinguish them from one another.
看一下下面这个图一下子就能理解,就是说每个节点左边的值一定小于右边。
了解到这个约束,这个题目解起来就比较简单了:
class Solution:
def trimBST(self, root, L, R):
"""
:type root: TreeNode
:type L: int
:type R: int
:rtype: TreeNode
"""
if(root.val < L):
if(root.right != None):
root = self.trimBST(root.right, L, R)
else:
return None
elif(root.val > R):
if(root.left != None):
root = self.trimBST(root.left, L, R)
else:
return None
else:
if(root.left != None):
root.left = self.trimBST(root.left, L, R)
else:
root.left = None
if(root.right != None):
root.right = self.trimBST(root.right, L, R)
else:
root.right = None
return root
BST数据结构的一些算法特性
Algorithm | Average | Worst case |
---|---|---|
Space | O(n) | O(n) |
Search | O(log n) | O(n) |
Insert | O(log n) | O(n) |
Delete | O(log n) | O(n) |
参考资料:
1、Leetcode
2、Wiki Binary search tree
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击