给出一棵二叉树的先序和中序排列,求解它的后序序列。
时间: 2023-04-22 18:06:56 浏览: 124
这道题需要用到二叉树的遍历方法。先序遍历的顺序是:根节点、左子树、右子树;中序遍历的顺序是:左子树、根节点、右子树;后序遍历的顺序是:左子树、右子树、根节点。
我们可以根据先序和中序遍历的结果,确定根节点的位置,然后将树分成左右两个子树,分别递归求解左右子树的后序遍历,最后将左右子树的后序遍历结果合并,再加上根节点,就得到了整棵树的后序遍历结果。
具体实现方法可以参考以下代码:
```python
def build_tree(preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
idx = inorder.index(root_val)
root.left = build_tree(preorder[1:idx+1], inorder[:idx])
root.right = build_tree(preorder[idx+1:], inorder[idx+1:])
return root
def postorder_traversal(root):
if not root:
return []
res = []
res += postorder_traversal(root.left)
res += postorder_traversal(root.right)
res.append(root.val)
return res
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]
```
其中,`build_tree`函数用于构建二叉树,`postorder_traversal`函数用于求解后序遍历序列。
阅读全文