由树的先序遍历序列和中序遍历序列创建一棵二叉树。
时间: 2024-04-26 11:15:57 浏览: 78
从前序与中序遍历序列构造二叉树1
5星 · 资源好评率100%
根据给定的先序遍历序列和中序遍历序列,可以通过递归的方式创建一棵二叉树。具体步骤如下:
1. 根据先序遍历序列,确定根节点,创建一个根节点。
2. 在中序遍历序列中找到根节点的位置,根节点左边的部分为左子树的中序遍历序列,右边的部分为右子树的中序遍历序列。
3. 根据左子树的中序遍历序列和左子树的先序遍历序列,递归创建左子树。
4. 根据右子树的中序遍历序列和右子树的先序遍历序列,递归创建右子树。
5. 将左子树和右子树分别作为根节点的左右子树。
下面是Python代码实现:
```python
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder:
return None
root = TreeNode(preorder[0])
mid_idx = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1:mid_idx+1], inorder[:mid_idx])
root.right = self.buildTree(preorder[mid_idx+1:], inorder[mid_idx+1:])
return root
```
阅读全文