Binary Search Tree 以及一道 LeetCode 题目

一道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.

由于对于 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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java进阶架构师

对HashMap的思考及手写实现

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

1032
来自专栏小灰灰

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

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

2716
来自专栏项勇

笔记72 | 将姓放在名的后面,排序按姓氏首字母排列的修改笔记

1865
来自专栏云瓣

前端中常见数据结构小结

数据结构在开发中是一种编程思想的提炼,无关于用何种语言开发或者是哪种端开发。下列将笔者涉猎到的与前端相关的数据结构案例作如下总结:

721
来自专栏软件开发 -- 分享 互助 成长

二分查找

二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列...

2177
来自专栏Java学习网

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

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

7916
来自专栏微信公众号:Java团长

对HashMap的思考及手写实现

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

841
来自专栏我是业余自学C/C++的

队列

队列和栈一样,是一种特殊的线性表。跟栈不同的是,队列的插入和删除分别在线性表的两端进行,因此,队列是一个先进先出(FIFO)的线性表。插入元素的一端叫队尾(ba...

811
来自专栏面朝大海春暖花开

oracle递归查询

这个子句主要是用于B树结构类型的数据递归查询,给出B树结构类型中的任意一个结点,遍历其最终父结点或者子结点。

4013
来自专栏Java帮帮-微信公众号-技术文章全总结

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

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

40411

扫码关注云+社区

领取腾讯云代金券