第一行为二叉树的中序序列第二行为二叉树的后序序列输出数据一行为二叉树的先序序列
根据中序序列和后序序列构建二叉树的过程如下:
- 后序序列的最后一个元素为根节点。
- 在中序序列中找到根节点的位置,将中序序列分为左子树和右子树。
- 根据左子树的元素个数,在后序序列中将左子树和右子树分开。
- 递归地构建左子树和右子树。
根据上述过程,可以使用递归算法来构建二叉树,并输出先序序列。
下面是使用Python实现的代码:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(inorder, postorder):
if not inorder:
return None
# 后序序列的最后一个元素为根节点
root_val = postorder[-1]
root = TreeNode(root_val)
# 在中序序列中找到根节点的位置
inorder_idx = inorder.index(root_val)
# 根据左子树的元素个数,在后序序列中将左子树和右子树分开
left_inorder = inorder[:inorder_idx]
right_inorder = inorder[inorder_idx+1:]
left_postorder = postorder[:inorder_idx]
right_postorder = postorder[inorder_idx:-1]
# 递归地构建左子树和右子树
root.left = buildTree(left_inorder, left_postorder)
root.right = buildTree(right_inorder, right_postorder)
return root
def preorderTraversal(root):
if not root:
return []
# 先序序列:根节点 -> 左子树 -> 右子树
return [root.val] + preorderTraversal(root.left) + preorderTraversal(root.right)
# 输入中序序列和后序序列
inorder = input().split()
postorder = input().split()
# 构建二叉树
root = buildTree(inorder, postorder)
# 输出先序序列
preorder = preorderTraversal(root)
print(' '.join(map(str, preorder)))
注意:上述代码中,假设输入的中序序列和后序序列中的元素都是不重复的
原文地址: https://www.cveoy.top/t/topic/hQ67 著作权归作者所有。请勿转载和采集!