后序+中序序列构造二叉树 输入样例: 第一行输入序列长度n,第二行输入n个字符表示二叉树后序遍历的序列,第三行输入n个字符表示二叉树中序遍历的序列
时间: 2023-05-03 17:00:52 浏览: 119
题目需要构造一个二叉树,输入样例如下:
第一行输入序列长度n,第二行输入n个字符表示二叉树后序遍历的序列,第三行输入n个字符表示二叉树中序遍历的序列。
首先建立二叉树的节点类:
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
然后根据后序遍历和中序遍历的结果,构建二叉树:
def buildTree(postorder, inorder):
if not postorder: # 后序遍历为空,返回None
return None
node = Node(postorder[-1]) # 后序遍历序列的最后一个元素为根节点
idx = inorder.index(postorder[-1]) # 在中序遍历序列中找到根节点的位置
node.left = buildTree(postorder[:idx], inorder[:idx]) # 递归构建左子树
node.right = buildTree(postorder[idx:-1], inorder[idx+1:]) # 递归构建右子树
return node
最后输入样例,调用函数构造二叉树:
n = int(input()) # 读入序列长度n
postorder = input().strip() # 读入后序遍历序列
inorder = input().strip() # 读入中序遍历序列
root = buildTree(postorder, inorder) # 构造二叉树