编写程序解决的问题是:已知一个二叉树的前序遍历和中序遍历的结果,给出该二叉树的后序遍历的结果
时间: 2024-06-16 10:05:56 浏览: 203
编写程序解决的问题是根据给定的二叉树的前序遍历和中序遍历结果,求出该二叉树的后序遍历结果。
解决这个问题的一种常用方法是通过递归来构建二叉树。具体步骤如下:
1. 首先,根据前序遍历的结果确定根节点。前序遍历的第一个元素即为根节点。
2. 然后,在中序遍历结果中找到根节点的位置,将中序遍历结果分为左子树和右子树。
3. 接下来,分别对左子树和右子树进行递归操作,得到左子树的后序遍历结果和右子树的后序遍历结果。
4. 最后,将根节点放在后序遍历结果的最后。
以下是一个示例代码实现:
```python
def build_tree(preorder, inorder):
if not preorder or not inorder:
return []
root_val = preorder
root = TreeNode(root_val)
root_index = inorder.index(root_val)
left_preorder = preorder[1:root_index+1]
left_inorder = inorder[:root_index]
right_preorder = preorder[root_index+1:]
right_inorder = inorder[root_index+1:]
root.left = build_tree(left_preorder, left_inorder)
root.right = build_tree(right_preorder, right_inorder)
return root
def postorder_traversal(root):
if not root:
return []
result = []
result.extend(postorder_traversal(root.left))
result.extend(postorder_traversal(root.right))
result.append(root.val)
return result
# 示例调用
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]
阅读全文