已知前序中序求后序c++
时间: 2023-11-29 19:05:52 浏览: 36
好的,这是一个很经典的二叉树问题。我们可以通过递归的方式来解决这个问题。
具体来说,我们可以首先在前序遍历中找到根节点,然后在中序遍历中确定根节点的左子树和右子树的范围。接下来,我们可以分别递归地处理左子树和右子树,并将它们的后序遍历结果拼接起来,最后再加入根节点,就可以得到整个树的后序遍历结果。
这里有一份示例代码供参考:
```python
def build_postorder(preorder, inorder):
if not preorder or 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_postorder(left_preorder, left_inorder)
right_postorder = build_postorder(right_preorder, right_inorder)
return left_postorder + right_postorder + [root]
```
这个函数接受前序遍历和中序遍历的结果作为参数,返回后序遍历的结果。注意,这里使用了 Python 中列表的切片操作来快速分割数组,以及 index 方法来查找根节点在中序遍历中的位置。