根据前序遍历和中序遍历建树,不用指针
时间: 2023-07-05 17:29:56 浏览: 116
可以使用递归和切片来构建二叉树,不需要使用指针。具体实现思路如下:
1. 首先根据前序遍历序列的第一个元素确定根节点。
2. 然后在中序遍历序列中找到根节点的位置,根节点左边的部分即为左子树的中序遍历序列,右边的部分即为右子树的中序遍历序列。
3. 根据左子树的中序遍历序列长度,从前序遍历序列中分离出左子树的前序遍历序列和右子树的前序遍历序列。
4. 递归处理左子树和右子树,分别构造左子树和右子树,并将它们连接到根节点上。
具体的代码实现如下:
```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)
idx = inorder.index(root_val)
left_inorder = inorder[:idx]
right_inorder = inorder[idx+1:]
left_preorder = preorder[1:1+len(left_inorder)]
right_preorder = preorder[1+len(left_inorder):]
root.left = buildTree(left_preorder, left_inorder)
root.right = buildTree(right_preorder, right_inorder)
return root
```
使用示例:
```python
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
root = buildTree(preorder, inorder)
```
该代码将会创建如下的二叉树:
```
3
/ \
9 20
/ \
15 7
```
阅读全文