python二叉搜索函数 python 二叉搜索树

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

python打印二叉树所有路径的主函数怎样写

基本算法就是二叉树的遍历，首先想到的是深度优先遍历。

难点在于，如何实现每个子路径的记录和append

binaryTreePaths函数只给了root变量，无法存储每个子路径，考虑写辅助函数res，添加存储路径的变量

res(root,temp)

同时还需要一个全局变量result存储最后的输出结果，result.append(temp)

相关问答

Q1: 783. 二叉搜索树结点最小距离（Python）

难度：★☆☆☆☆

类型：二叉树

给定一个二叉搜索树的根结点 root, 返回树中任意两节点的差的最小值。

注意

二叉树的大小范围在 2 到 100。

二叉树总是有效的，每个节点的值都是整数，且不重复。

示例

输入: root = [4,2,6,1,3,null,null]

输出: 1

解释:

注意，root是树结点对象(TreeNode object)，而不是数组。

给定的树 [4,2,6,1,3,null,null] 可表示为下图:

最小的差值是 1, 它是节点1和节点2的差值, 也是节点3和节点2的差值。

二叉搜索树有一个重要的性质：二叉搜索树的中序遍历是升序序列。因此我们可以通过将二叉搜索树序列化，然后计算最小相邻元素差。

另一种解法，我们可以在中序遍历的同时记录最小差值：

如有疑问或建议，欢迎评论区留言~

Q2: python 二分查找算法函数bi_search(),该函数实现检索任意一个整数在 prime() 函数生成的

def prime(n):

if n=2:

return []

result=[False,False]+[True]*(n-2)

for i in range(len(result)):

if result[i]==True:

for j in range(2*i,len(result),i):

result[j]=False

return [i for i in range(len(result)) if result[i]==True]

def bi_search(prime,primelist,start,end):

if startend :

return -1

mid=(start+end)//2

if primelist[mid]==prime:

return mid

elif primelist[mid]prime:

end=mid-1

else:

start=mid+1

return bi_search(prime,primelist,start,end)

if __name__=='__main__':

n=int(raw_input())

primelist=prime(n)

num=raw_input()

while num:

num=int(num)

index=bi_search(num,primelist,0,len(primelist)-1)

print(index)

num=raw_input()

Q3: 一文秒懂python正则表达式常用函数

01 Re概览

Re模块是python的内置模块，提供了正则表达式在python中的所有用法，默认安装位置在python根目录下的Lib文件夹（如 ..\Python\Python37\Lib）。主要提供了3大类字符串操作方法：

字符查找/匹配

字符替换

字符分割

由于是面向字符串类型的模块，就不得不提到字符串编码类型。re模块中，模式串和搜索串既可以是 Unicode 字符串 (常用str类型) ，也可以是8位字节串 (bytes，2位16进制数字，例如\xe5) ，但要求二者必须是同类型字符串。

02 字符串查找/匹配

预编译：compile

在介绍查找和匹配函数前，首先需要知道re的compile函数，该函数可以将一个模式串编译成正则表达式类型，以便后续快速匹配和复用

import re pattern = re.compile(r'[a-z]{2,5}') type(pattern) #re.Pattern

此例创建了一个正则表达式式对象 (re.pattern) ，命名为pattern，用于匹配2-5位小写字母的模式串。后续在使用其他正则表达式函数时，即可使用pattern进行方法调用。

匹配：match

match函数用于从文本串的起始位置开始匹配，若匹配成功，则返回相应的匹配对象，此时可调用group()方法返回匹配结果，也可用span()方法返回匹配起止下标区间；否则返回None

import re pattern = re.compile(r'[a-z]{2,5}') text1 = 'this is a re test' res = pattern.match(text1) print(res) # if res: print(res.group()) #this print(res.span()) #(0, 4) text2 = '是的, this is a re test' print(pattern.match(text2))#None

match函数还有一个变形函数fullmatch，当且仅当模式串与文本串刚好全部匹配时，返回一个匹配对象，否则返回None

搜索：search

match只提供了从文本串起始位置匹配的结果，如果想从任意位置匹配，则可调用search方法，与match方法类似，当任意位置匹配成功，则立即返回一个匹配对象，也可调用span()方法获取起止区间、调用group方法获得匹配文本串

import re pattern = re.compile(r'\s[a-z]{2}') text1 = 'this is a re test' res = pattern.search(text1) print(res) # if res: print(res.group()) #is print(res.span()) #(4, 7) pattern2 = re.compile(r'\s[a-z]{5}') text2 = '是的,this is a re test' print(pattern2.search(text2))#None

match和search均用于匹配单个结果，唯一区别在于前者是从起始位置开始匹配，而后者从任意位置匹配，匹配成功则返回一个match对象。

全搜索：findall/finditer

几乎是最常用的正则表达式函数，用于寻找所有匹配的结果，例如在爬虫信息提取中，可非常方便地提取所有匹配字段

import re pattern = re.compile(r'\s[a-z]{2,5}') text1 = 'this is a re test' res = pattern.findall(text1) print(res) #[' is', ' re', ' test']

findall返回的是一个列表对象类型，当无匹配对象时，返回一个空列表。为了避免因同时返回大量匹配结果占用过多内存，可以调用finditer函数返回一个迭代器类型，其中每个迭代元素是一个match对象，可继续调用group和span方法获取相应结果

import re pattern = re.compile(r'\s[a-z]{2,5}') text1 = 'this is a re test' res = pattern.finditer(text1) for r in res: print(r.group()) """ is re test """

当匹配模式串较为简单或者仅需单词调用时，上述所有方法也可直接调用re类函数，而无需事先编译。此时各方法的第一个参数为模式串。

import re pattern = re.compile(r'\d{2,5}') text = 'this is re test' re.findall('[a-z]+', text) #['this', 'is', 're', 'test'] 03 字符串替换/分割

替换:sub/subn

当需要对文本串进行条件替换时，可调用re.sub实现 (当然也可先编译后再用调用实例方法) ，相应参数分别为模式串、替换格式、文本串，还可以通过增加缺省参数限定替换次数和匹配模式。通过在模式串进行分组，可实现字符串的格式化替换（类似字符串的format方法），以实现特定任务。

import re text = 'today is 2020-03-05' print(re.sub('-', '', text)) #'today is 20200305' print(re.sub('-', '', text, 1)) #'today is 202003-05' print(re.sub('(\d{4})-(\d{2})-(\d{2})', r'\2/\3/\1', text)) #'today is 03/05/2020'

re.sub的一个变形方法是re.subn，区别是返回一个2元素的元组，其中第一个元素为替换结果，第二个为替换次数

import re text = 'today is 2020-03-05' print(re.subn('-', '', text)) #('today is 20200305', 2)

分割：split

还可以调用正则表达式实现字符串的特定分割，相当于.split()方法的一个加强版，实现特定模式的分割，返回一个切割后的结果列表

import re text = 'today is a re test, what do you mind?' print(re.split(',', text)) #['today is a re test', ' what do you mind?'] 04 总结

python中的re模块提供了正则表达式的常用方法，每种方法都包括类方法调用(如re.match)或模式串的实例调用(pattern.match)2种形式

常用的匹配函数：match/fullmatch

常用的搜索函数：search/findall/finditer

常用的替换函数：sub/subn

常用的切割函数：split

还有其他很多方法，但不是很常用，具体可参考官方文档

另外，python还有第三方正则表达式库regex可供选择