由二叉树的前序序列和中序序列求后序序列,请用Python代码实现
时间: 2023-04-07 20:04:21 浏览: 93
以下是Python代码实现:
```python
def build_tree(preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder[0]
root_index = inorder.index(root_val)
left_inorder = inorder[:root_index]
right_inorder = inorder[root_index+1:]
left_preorder = preorder[1:1+len(left_inorder)]
right_preorder = preorder[1+len(left_inorder):]
left_tree = build_tree(left_preorder, left_inorder)
right_tree = build_tree(right_preorder, right_inorder)
return TreeNode(root_val, left_tree, right_tree)
def postorder_traversal(root):
if not root:
return []
left = postorder_traversal(root.left)
right = postorder_traversal(root.right)
return left + right + [root.val]
preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
root = build_tree(preorder, inorder)
postorder = postorder_traversal(root)
print(postorder)
```
输出结果为:[4, 5, 2, 6, 7, 3, 1]