Python二叉搜索树与双向链表转换算法示例
作者:hustfc 时间:2023-07-17 22:49:42
本文实例讲述了Python二叉搜索树与双向链表转换算法。分享给大家供大家参考,具体如下:
题目描述
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
普通的二叉树也可以转换成双向链表,只不过不是排序的
思路:
1. 与中序遍历相同
2. 采用递归,先链接左指针,再链接右指针
代码1,更改doubleLinkedList,最后返回list的第一个元素:
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def lastElem(self, list):
if len(list) == 0:
return None
else: return list[len(list) - 1]
def ConvertCore(self, pRoot, doubleLinkedList):
if pRoot:
if pRoot.left:
self.ConvertCore(pRoot.left, doubleLinkedList)
pRoot.left = self.lastElem(doubleLinkedList)
if self.lastElem(doubleLinkedList):
self.lastElem(doubleLinkedList).right = pRoot
doubleLinkedList.append(pRoot)
if pRoot.right:
self.ConvertCore(pRoot.right, doubleLinkedList)
def Convert(self, pRootOfTree):
if pRootOfTree == None:
return None
doubleLinkedList = []
self.ConvertCore(pRootOfTree, doubleLinkedList)
return doubleLinkedList[0]
代码2,lastListNode指向双向链表中的最后一个节点,因此每次操作最后一个节点。这里要更改值,因此采用list的形式。
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def ConvertCore(self, pRoot, lastListNode):
if pRoot:
if pRoot.left:
self.ConvertCore(pRoot.left, lastListNode)
pRoot.left = lastListNode[0]
if lastListNode[0]:
lastListNode[0].right = pRoot
lastListNode[0] = pRoot
if pRoot.right:
self.ConvertCore(pRoot.right, lastListNode)
def Convert(self, pRootOfTree):
# write code here
if pRootOfTree == None:
return None
lastListNode = [None]
self.ConvertCore(pRootOfTree, lastListNode)
while lastListNode[0].left:
lastListNode[0] = lastListNode[0].left
return lastListNode[0]
希望本文所述对大家Python程序设计有所帮助。
来源:https://blog.csdn.net/weixin_36372879/article/details/84258821
标签:Python,二叉搜索树,双向链表
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
python做图片搜索引擎并保存到本地详情
2021-08-27 01:42:33
![](https://img.aspxhome.com/file/2023/2/66842_0s.png)
PPOCRLabel标注的txt格式如何转换成labelme能修改的json格式
2021-08-31 06:01:45
![](https://img.aspxhome.com/file/2023/7/107087_0s.jpg)
Python创建7种不同的文件格式的方法总结
2021-01-24 03:13:51
![](https://img.aspxhome.com/file/2023/2/120942_0s.png)
vue实现动态路由详细
2024-05-05 09:25:19
PHP simplexml_load_file()函数讲解
2023-06-03 23:16:56
![](https://img.aspxhome.com/file/2023/2/55402_0s.png)
Tensorflow使用tfrecord输入数据格式
2022-06-18 22:55:40
科学知识:时间复杂度计算方法
2023-09-18 21:42:28
MySQL定时备份之使用Linux下的crontab定时备份实例
2024-01-18 01:43:52
Python项目跨域问题解决方案
2022-12-01 17:39:32
pandas去重复行并分类汇总的实现方法
2021-06-12 17:38:37
![](https://img.aspxhome.com/file/2023/5/115825_0s.png)
python WindowsError的错误代码详解
2021-09-03 18:58:45
python实现将多个文件分配到多个文件夹的方法
2023-04-13 20:48:46
ASP和MYSQL开发网站的注意事项
2009-08-21 13:23:00
EasyASP v1.5发布(包含数据库操作类,原clsDbCtrl.asp)第1/2页
2011-04-08 10:40:00
判断目标是否是window,document,和拥有tagName的Element的代码
2024-04-16 08:46:46
Python实现GUI学生管理系统的示例代码
2022-06-01 01:47:56
5个CSS3技术实现设计增强
2009-09-04 17:04:00
Python实现学生管理系统的代码(JSON模块)
2022-01-02 07:54:42
![](https://img.aspxhome.com/file/2023/6/81626_0s.png)
Pytest框架之fixture详解(三)
2023-06-20 12:05:27
![](https://img.aspxhome.com/file/2023/1/65861_0s.png)
在Python中使用AOP实现Redis缓存示例
2021-09-12 11:18:45