已知一个二叉树的中序遍历序列和前序遍历序列,求这棵树的后序遍历序列。
时间: 2023-04-27 07:04:12 浏览: 107
利用二叉树中序及先序遍历确定该二叉树的后序序列
3星 · 编辑精心推荐
根据二叉树的遍历方式,我们可以知道前序遍历序列的第一个元素一定是根节点,而中序遍历序列中根节点左边的元素都是左子树的节点,右边的元素都是右子树的节点。因此,我们可以根据前序遍历序列中的根节点,将中序遍历序列分成左子树和右子树两部分。
接下来,我们可以递归地处理左子树和右子树,直到只剩下一个节点或者为空。最后,我们将左子树和右子树的后序遍历序列拼接起来,再加上根节点,就得到了整棵树的后序遍历序列。
具体实现可以参考以下代码:
```python
def build_tree(inorder, preorder):
if not inorder:
return []
root = preorder[0]
index = inorder.index(root)
left_inorder = inorder[:index]
right_inorder = inorder[index+1:]
left_preorder = preorder[1:1+len(left_inorder)]
right_preorder = preorder[1+len(left_inorder):]
left_postorder = build_tree(left_inorder, left_preorder)
right_postorder = build_tree(right_inorder, right_preorder)
return left_postorder + right_postorder + [root]
inorder = [4, 2, 5, 1, 6, 3, 7]
preorder = [1, 2, 4, 5, 3, 6, 7]
postorder = build_tree(inorder, preorder)
print(postorder) # [4, 5, 2, 6, 7, 3, 1]
```
这里我们定义了一个 `build_tree` 函数,它接受中序遍历序列和前序遍历序列作为参数,返回后序遍历序列。在函数中,我们首先判断中序遍历序列是否为空,如果是,则返回一个空列表。否则,我们取前序遍历序列的第一个元素作为根节点,找到它在中序遍历序列中的位置,将中序遍历序列分成左子树和右子树两部分。然后,我们递归地处理左子树和右子树,得到它们的后序遍历序列。最后,我们将左子树和右子树的后序遍历序列拼接起来,再加上根节点,就得到了整棵树的后序遍历序列。
阅读全文