根据给定二叉树的先序遍历和中序遍历结果,给出后序遍历,并写出代码
时间: 2024-10-19 10:09:19 浏览: 50
根据二叉树的先序遍历(根-左-右)和中序遍历(左-根-右),可以恢复出原始二叉树结构。然后通过后序遍历(左-右-根)的特点,我们可以逆向构建二叉树并得到后序遍历的结果。下面是一个简单的Python代码示例:
```python
def build_tree(preorder, inorder):
if not preorder or not inorder:
return None
# 先序遍历的第一个元素是根节点
root_val = preorder[0]
root = TreeNode(root_val)
# 找到根节点在中序遍历中的位置
root_in_order_idx = inorder.index(root_val)
# 分别对左右子树递归构造
root.left = build_tree(preorder[1:root_in_order_idx + 1], inorder[:root_in_order_idx])
root.right = build_tree(preorder[root_in_order_idx + 1:], inorder[root_in_order_idx + 1:])
return root
# 后续遍历时的辅助函数,用于获取剩余的元素列表
def postorder_traversal(node, result=None):
if node is None:
return []
if result is None:
result = []
result.extend(postorder_traversal(node.left))
result.extend(postorder_traversal(node.right))
# 将当前节点添加到后序遍历结果的最前面
result.insert(0, node.val)
return result
# 假设我们有预序遍历 `preorder` 和中序遍历 `inorder`
preorder = [1, 2, 4, 5, 3, 6] # 示例
inorder = [4, 2, 5, 1, 6, 3]
root = build_tree(preorder, inorder)
postorder = postorder_traversal(root)
print("后序遍历的结果为:", postorder)
```
在这个代码中,首先通过先序遍历找到根节点,再利用中序遍历来确定根节点的位置。接着递归地构建左右子树。最后通过后序遍历的顺序(左-右-根)获取完整的后序遍历序列。
阅读全文