Binary Search Tree 以及一道 LeetCode 题目

一道LeetCode题目

Given a binary search tree and the lowest and highest boundaries as `L` and `R`, 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.

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```

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)

362 篇文章32 人订阅

0 条评论

相关文章

对HashMap的思考及手写实现

HashMap是Java中常用的集合，而且HashMap的一些思想，对于我们平时解决业务上的一些问题，在思路上有帮助，基于此，本篇博客将分析HashMap底层设...

1032

JDK容器学习之TreeMap (二) : 使用说明

TreeMap 使用说明 TreeMap 的底层数据结构为红黑树，主要是根据key进行排序，相比较于HashMap的数组+链表+红黑树的数据结构而言，两者的应...

2716

1865

721

Java中三种Set类型用法、性能大比拼

Java为开发者提供了大量的工具类，这给开发人员带来了很大方便，但是选择多了也有困扰，究竟用哪个类；我想选择什么，一是看自己具体需求，二是类本身的性能和用法；J...

7916

对HashMap的思考及手写实现

HashMap是Java中常用的集合，而且HashMap的一些思想，对于我们平时解决业务上的一些问题，在思路上有帮助，基于此，本篇博客将分析HashMap底层设...

841

4013

【Java提高十九】Iterator&fail-fast机制

【Java提高十九】Iterator&fail-fast机制 Iterator详解 迭代对于我们搞Java的来说绝对不陌生。我们常常使用JDK提供的迭代接口进行...

40411