现在给出一颗二叉树的先序遍历序列和中序遍历序列,试着找出它的后序遍历序列。
时间: 2023-07-24 14:05:59 浏览: 93
给出先序遍历和中序遍历,求二叉树后序遍历
5星 · 资源好评率100%
假设给定的二叉树先序遍历序列为:ABDECF,中序遍历序列为:DBEAFC。
我们可以根据先序遍历序列的第一个元素 A,确定该二叉树的根节点。然后在中序遍历序列中找到 A 的位置,将其左边的所有元素作为左子树的中序遍历序列,右边的所有元素作为右子树的中序遍历序列。
根据左子树的中序遍历序列和先序遍历序列,可以递归构建出左子树。同理,根据右子树的中序遍历序列和先序遍历序列,可以递归构建出右子树。
最后,将根节点的值放在后序遍历序列的最后位置,左子树的后序遍历序列放在根节点值的左边,右子树的后序遍历序列放在根节点值的右边,即可得到该二叉树的后序遍历序列:DBEFCA。
具体实现可以写一个递归函数,代码如下:
```python
def build_tree(preorder, inorder):
if not preorder:
return []
root_val = preorder[0]
root = TreeNode(root_val)
mid = inorder.index(root_val)
root.left = build_tree(preorder[1:mid+1], inorder[:mid])
root.right = build_tree(preorder[mid+1:], inorder[mid+1:])
return root
def postorder_traversal(root):
if not root:
return []
left = postorder_traversal(root.left)
right = postorder_traversal(root.right)
return left + right + [root.val]
preorder = ['A', 'B', 'D', 'E', 'C', 'F']
inorder = ['D', 'B', 'E', 'A', 'F', 'C']
root = build_tree(preorder, inorder)
postorder = postorder_traversal(root)
print(postorder) # ['D', 'E', 'B', 'F', 'C', 'A']
```
阅读全文