根据前序和中序创建树
时间: 2024-02-05 19:12:18 浏览: 39
根据前序遍历和中序遍历构建二叉树的过程可以分为以下几个步骤:
1. 定位根节点。前序遍历的第一个元素就是根节点,将其从前序序列中取出来。
2. 在中序遍历中找到根节点的位置,根节点之前的序列为左子树的中序遍历结果,根节点之后的序列为右子树的中序遍历结果。
3. 由于前序遍历中已经取出了根节点,因此接下来的前序遍历序列中,前面一部分是左子树的前序遍历结果,后面一部分是右子树的前序遍历结果。
4. 分别递归构建左子树和右子树。
下面是具体的实现代码(Python):
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder, inorder):
if not preorder or not inorder:
return None
# 根节点在前序遍历序列的第一个位置
root_val = preorder[0]
root = TreeNode(root_val)
# 在中序遍历序列中找到根节点的位置
mid = inorder.index(root_val)
# 递归构建左子树和右子树
root.left = buildTree(preorder[1:mid+1], inorder[:mid])
root.right = buildTree(preorder[mid+1:], inorder[mid+1:])
return root
```
使用示例:
```python
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
root = buildTree(preorder, inorder)
```
构建后的二叉树结构如下:
```
3
/ \
9 20
/ \
15 7
```