已知一棵二叉树的前序遍历和后序遍历求中序遍历
时间: 2023-07-08 09:54:25 浏览: 138
假设这棵二叉树的前序遍历为preorder,后序遍历为postorder,那么可以通过递归的方式求出中序遍历。
具体做法如下:
1. 首先,从前序遍历中取出第一个元素作为根节点。
2. 然后,在后序遍历中找到根节点的位置,将后序遍历分为左子树和右子树。
3. 接着,递归地对左子树和右子树进行同样的操作,直到遇到空树为止。
4. 最后,将左子树、根节点、右子树依次输出,即为中序遍历。
下面是示例代码实现(以 Python 为例):
```python
def inorder(preorder, postorder):
if not preorder:
return []
root = preorder[0]
inorder = []
if len(preorder) == 1:
inorder.append(root)
return inorder
left_root = preorder[1]
left_size = postorder.index(left_root) + 1
left_inorder = inorder(preorder[1:left_size+1], postorder[:left_size])
inorder.extend(left_inorder)
inorder.append(root)
right_inorder = inorder(preorder[left_size+1:], postorder[left_size:-1])
inorder.extend(right_inorder)
return inorder
```
其中,preorder 和 postorder 分别为前序遍历和后序遍历序列。函数返回中序遍历序列。
阅读全文
相关推荐















