给我python3代码,题目是这样的:给定节点数为 n 的二叉树的前序遍历和中序遍历结果,请重建出该二叉树并返回它的头结点。 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建出如下图所示。
时间: 2023-02-07 07:33:38 浏览: 90
Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例
5星 · 资源好评率100%
这是一个典型的二叉树重建问题。我们可以使用递归的方式来解决这个问题。
首先,根据前序遍历的第一个结点值,我们可以找到中序遍历中的对应结点。根据这个结点,我们可以将中序遍历划分成左子树和右子树两部分。
然后我们可以使用递归的方式来构建二叉树。对于当前的结点,我们先构建它的左子树,再构建它的右子树。
下面是代码:
```python
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def build_tree(preorder, inorder):
if not preorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
root_index = inorder.index(root_val)
left_inorder = inorder[:root_index]
right_inorder = inorder[root_index + 1:]
left_preorder = preorder[1:1 + len(left_inorder)]
right_preorder = preorder[1 + len(left_inorder):]
root.left = build_tree(left_preorder, left_inorder)
root.right = build_tree(right_preorder, right_inorder)
return root
```
使用方法:
```python
root = build_tree([1, 2, 4, 7, 3, 5, 6, 8], [4, 7, 2, 1, 5, 3, 8, 6])
```
这样,就可以得到一棵二叉树的根节点。
阅读全文