python写一个二叉树(Python二叉搜索树与双向链表转换算法示例)
类别:脚本大全 浏览量:2907
时间:2022-01-16 00:39:49 python写一个二叉树
Python二叉搜索树与双向链表转换算法示例本文实例讲述了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
您可能感兴趣
- vscode如何配置python环境(VSCode Python开发环境配置的详细步骤)
- python多线程超时设置(解决python线程卡死的问题)
- python将一个字符串逆序输出(Python字符串逆序输出的实例讲解)
- python群聊提示(python-itchat 统计微信群、好友数量,及原始消息数据的实例)
- python 爬虫图形验证码(Python爬虫实现验证码登录代码实例)
- pythonsocket编写web服务器(局域网内python socket实现windows与linux间的消息传送)
- python怎么测试api接口(python接口自动化测试之接口数据依赖的实现方法)
- python 后台django(Python Django给admin添加Action的方法实例详解)
- python技巧图解(Python魔法方法功能与用法简介)
- 怎么用python分析足球(使用Python进行体育竞技分析预测球队成绩)
- python中怎么连接mysql(python远程连接MySQL数据库)
- pythonmatplotlib散点图怎么画(python使用matplotlib画柱状图、散点图)
- python使用门算法加密文件(python实现栅栏加解密 支持密钥加密)
- python包和模块管理(python的依赖管理的实现)
- python指定路径创建txt文件(python根据txt文本批量创建文件夹)
- python ssh 连接(python pexpect ssh 远程登录服务器的方法)
- CellPress旗下的6 期刊,国人友刊来了解一下吧(CellPress旗下的6期刊国人友刊来了解一下吧)
- ()
- SCI检索 SSCI检索 EI检索 ISTP检索 CSCD检索简介(SCI检索SSCI检索EI检索)
- 参考文献里期刊名称的写法,你知道吗(参考文献里期刊名称的写法)
- 硕博期刊 SCI SSCI CSSCI分不清 一文带你看懂主流期刊分类(硕博期刊SCISSCI)
- 辱华品牌新百伦官宣新代言人IU,个别粉丝希望get爱豆同款(辱华品牌新百伦官宣新代言人IU)
热门推荐
- php怎么实现多线程(PHP实现的多进程控制demo示例)
- filezilla搭建ftp服务器英文(FileZilla Server FTP服务器安装使用图文教程)
- nginx配置404状态码(解决Nginx 配置 proxy_pass 后 返回404问题)
- web界面设计的建议
- iis部署后浏览没有主界面(IIS 浏览aspx页面出现无法显示XML页的解决方法分享)
- sql server 知识大全(sql server 交集,差集的用法详解)
- docker 容器经常启动失败(浅谈Docker run 容器处于created状态问题)
- apache连接tomcat配置(Apache结合Tomcat实现动静分离的方法)
- 常见的php五大运行模式详解(php设计模式之职责链模式定义与用法经典示例)
- dede标签调用大全(织梦dede所有实用标签调用方法搜集整理)
排行榜
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9