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
您可能感兴趣
- python多线程并发使用场景(对python多线程SSH登录并发脚本详解)
- python学生信息管理系统教程(学生信息管理系统Python面向对象版)
- python统计字符类型和数量(python统计中文字符数量的两种方法)
- python模块使用方法(详解python的argpare和click模块小结)
- python 串口图形化(python使用MQTT给硬件传输图片的实现方法)
- 如何用python做一个弹窗(python实现祝福弹窗效果)
- python线程池的实现原理(详解python中的线程与线程池)
- python教程第126节(Python 学习教程之networkx)
- python零基础入门详细教程(Python零基础入门学习之输入与输出)
- python代码添加微信号(python 获取微信好友列表的方法微信web)
- python如何遍历一个列表(说说如何遍历Python列表的方法示例)
- wxpython 弹出对话框显示图片(WxPython建立批量录入框窗口)
- pythonzipfile的用法(对Python之gzip文件读写的方法详解)
- pythonpulp怎么使用(pyhanlp安装介绍和简单应用)
- python中的insert(python assert的用处示例详解)
- python响应处理post请求(Python3模拟curl发送post请求操作示例)
- 怎么快速学好英语(怎么快速学好英语初中)
- 中国留学生都是富二代吗()
- 我们现在吃的苹果是哪里来的 原来现代苹果引入中国仅有一百多年(我们现在吃的苹果是哪里来的)
- 买绿宝不能只挑黄绿色 菜农教你3招挑,个个皮薄肉脆,香甜爆汁(买绿宝不能只挑黄绿色)
- 大果肉搭配薄瓜皮, 绿宝 脆甜爽口,不愧是甜瓜中的 佼佼者(大果肉搭配薄瓜皮)
- 河南尉氏县因地制宜发展果蔬种植 水坡镇绿宝甜瓜变 金瓜(河南尉氏县因地制宜发展果蔬种植)
热门推荐
- django测试服务器静态资源放哪里(Django使用redis缓存服务器的实现代码示例)
- python3.5 tkinter教程(解决python3.5 正常安装 却不能直接使用Tkinter包的问题)
- datatable和list的转换
- dedecms首页布局(dedecms实现列表页缩略图随机调用的方法)
- python封装函数讲解(Python中super函数用法实例分析)
- redis新手入门教学(scrapy-redis的安装部署步骤讲解)
- dedecms提示怎么去除(DEDECMS网站被挂马的解决办法)
- python图书馆管理系统源码(python实现图书借阅系统)
- dockernacos教程(Docker+nacos+seata1.3.0安装与使用配置教程)
- sqlserver索引实例(SQL Server索引的原理深入解析)
排行榜
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9