程序地带

【菜鸡新手 - 牛客网刷题NC45】 python 根据 前序遍历序列 & 中序遍历序列 生成二叉树 || 二叉树 前、中、后 、层序 遍历 的【递归 】& 【迭代】 || python


以下为原创代码,可以参考,但禁止转载! @ author:yhr



目录
根据 前序遍历序列 & 中序遍历序列 生成二叉树递归 : 三种遍历迭代 : 三种遍历层序遍历调用示例


根据 前序遍历序列 & 中序遍历序列 生成二叉树
#coding=utf-8
#__author__='YHR'
import copy
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def findNumIndex( L, key):
# 找到L列表中,key的 index
length = len(L)
for _ in range(length):
if L[_] == key:
return _
return -1
def reConstructBinaryTree(pre, tin):
if len(pre) < 1 or len(tin) < 1:
return None
else:
pre = copy.deepcopy(pre);
tin = copy.deepcopy(tin)
headval = pre[0]
# get 左子树的tin:tinLeft and 右子树的tin:tinRight
tinHeadIndex = findNumIndex(tin, headval) # 找到父节点的 index
if tinHeadIndex > 0:
tinLeftTree = tin[0:tinHeadIndex]
else:
tinLeftTree = []
if tinHeadIndex < len(tin) - 1:
tinRightTree = tin[tinHeadIndex + 1:]
else:
tinRightTree = []
# get 左子树的pre:preleft and 右子树的pre:preRight
if len(tinLeftTree) >= 1:
preLeftTree = pre[1:1 + len(tinLeftTree)]
else:
preLeftTree = []
if len(tinRightTree) >= 1:
preRightTree = pre[1 + len(tinLeftTree):]
else:
preRightTree = []
parentNode = TreeNode(x=headval)
# left child tree
parentNode.left = reConstructBinaryTree(preLeftTree, tinLeftTree)
# right child tree
parentNode.right = reConstructBinaryTree(preRightTree, tinRightTree)
return parentNode
递归 : 三种遍历
#coding=utf-8
#__author__='YHR'
class Solution:
def threeOrders(self, root):
# write code here
pass
def digui_pre_order(self, root):
# 头 左右
preorder = []
if root is not None:
preorder += [root.val]
preorder += (self.digui_pre_order(root.left))
preorder += (self.digui_pre_order(root.right))
else:
pass
return preorder
def digui_mid_order(self, root):
# 左 头 右
midorder = []
if root is not None:
midorder += self.digui_mid_order(root.left)
midorder += [root.val]
midorder += self.digui_mid_order(root.right)
else:
pass
return midorder
def digui_post_order(self, root):
# 左 右 头
postorder = []
if root is not None:
postorder += self.digui_post_order(root.left)
postorder += self.digui_post_order(root.right)
postorder += [root.val]
else:
pass
return postorder
迭代 : 三种遍历
#coding=utf-8
#__author__='YHR'
# ---------------------- no digui ---------------------
def nodigui_pre_order(self, root):
# 头 左右
stack=[]
pre_order = []
if root is None:
return pre_order
else:
stack.insert(0, root)
while len(stack) > 0:
node = stack.pop(0)
pre_order.append(node.val)
if node.right is not None:
stack.insert(0, node.right)
if node.left is not None:
stack.insert(0, node.left)
return pre_order
# 不需要递归
def nodigui_mid_order(self, root):
# 左 头 右
stack = []
mid_order = []
if root is None:
return mid_order
else:
top = root
stack.insert(0, top)
while len(stack) > 0 :
while top.left is not None:
stack.insert(0, top.left)
top = top.left
while len(stack)>0:
# while 直到出现 右孩子,或者出栈完毕为止,不走回头路即不走已经遍历过的左孩子
# 不加while的话,top弹出以后 如果此时是非叶子节点, 他没有right节点,存在左孩子
# 他就会继续压入他的左孩子。但是他的左孩子已经被压进去过了,就会循环
top = stack.pop(0)
mid_order.append(top.val)
if top.right is not None:
stack.insert(0, top.right)
top = top.right
break
return mid_order
def nodigui_post_order(self, root):
# 左 右 头
stack = []
post_order = []
if root is None:
return post_order
else:
top = [root, 1]
# top[1] 为遍历到top[0]的次数 count, 第一次遍历到它, count=1,入栈,遍历左孩子
# 第二次遍历到它, count=2 入栈,遍历右孩子
# count=2 时,再次遍历到他,表示第3次遍历到它, 终于可以真正出栈啦~~~
stack.insert(0, top)
while len(stack) > 0:
while top[0].left is not None:
new = [top[0].left, 1]
stack.insert(0, new)
top = new
while len(stack) > 0:
top = stack.pop(0)
if top[1] == 2:
post_order.append(top[0].val)
else:
top = [top[0], 2]
stack.insert(0, top)
if top[0].right is not None:
new = [top[0].right, 1]
stack.insert(0, new)
top = new
break
return post_order
层序遍历
def cengxuTraverse(root):
# 层序遍历
if root is None:
return []
else:
queue = []
cengxu = []
queue.append(root)
while len(queue) > 0:
node = queue.pop(0) # 弹出队首元素
cengxu.append(node.val)
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
return cengxu
调用示例
#coding=utf-8
#__author__='YHR'
if __name__=='__main__':
pre, tin = [44,18,22,40,34,36,31,1,41,30,19,27,16,32,9,3,12,39,20,4,11,10,38,7,23,8,42,35,28,2,14,6,24,15,43,5,33,26,21,17,29,13,25,37],
[40,31,36,34,22,18,30,19,41,32,16,27,1,3,12,9,4,20,39,11,44,23,42,8,7,35,28,38,10,15,24,43,26,33,5,6,14,2,29,17,13,21,25,37]
root = reConstructBinaryTree(pre, tin) #根据pre and tin 生成二叉树
print(cengxuTraverse(root))
s = Solution()
print(s.nodigui_pre_order(root))
print(s.nodigui_mid_order(root))
print(s.nodigui_post_order(root))

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Aka_Happy/article/details/112689236

随机推荐

动态文本_办公小技巧:PPT制作超酷动态图

动态文本_办公小技巧:PPT制作超酷动态图

在我们制作的PPT里边,如果标题或目录文字能够“动起来”的话,一定会为PPT文档增色不少。下面笔者就给大家介绍几点经验,以实现让PPT中的文字“动起来”的效果...

小猪佩琪168 阅读(392)

博客园贴边打赏

博客园贴边打赏

目录前言贴边打赏美化二维码合并二维码压缩二维码贴边代码加到博客园博客园效果总结前言玩博客园到网上找各种美化博客和主题啥的,找到一些好玩的东西,比如打赏插件。我一开始也是用的别人现成的插件,但是觉得过于...

janbar 阅读(172)

【计算机网络】物理层

【计算机网络】物理层

物理层1.物理层的基本概念1.1物理层主要目的1.2物理层主要任务2.数据通信的基础知识2.1典型的数据通信模型2.2数据通信相关术语2.3三种通信方式2.4两种数据传输方式2.5速率2.6带宽2.7...

BitterSweet_1218 阅读(146)

jquery多库共存

<!DOCTYPEhtml><html><head><metacharset="utf-8"/><metaname="...

thomas_blog 阅读(910)

C++ 函数对象

#include<iostream>#include<map>#include<functional>#include<forward_list>#in...

zxcvb036 阅读(388)

变量、判断和重复动作

变量、判断和重复动作

变量与算数POSIXshell为内嵌算数提供了一种标记法,称为算数展开Shell会对$(…)里面的算数表达式进行计算,在将计算后的结果放回到命令的文本内容变量赋值予环境re...

tt_ndyd 阅读(735)

智能化漏洞挖掘技术总结

智能化漏洞挖掘技术总结

全文基于《从自动化到智能化:软件漏洞挖掘技术进展》进行提炼、总结、修改。1.静态漏洞挖掘技术1.1面向源代码面向源代码的漏洞挖掘主要采用基于中间表示的分析和基于逻辑推理的分析技术。基于中间表示的分析技...

Neil-Yale 阅读(707)

JS获取前一页面链接的参数值

//前一页面的链接传参window.lo.href="xxxx.aspx?IdNumber="+IDENTITYCARD;第一种方法://当前页面获取参数值方法functionge...

Stranger。 阅读(897)