编写算法根据二叉树的前序序列和中序序列建立二叉树。
时间: 2024-05-04 15:17:05 浏览: 12
这道题目可以通过递归来实现,具体步骤如下:
1. 前序序列的第一个元素即为二叉树的根节点;
2. 在中序序列中找到根节点的位置,根节点左边的序列即为左子树的中序序列,右边的序列为右子树的中序序列;
3. 根据左子树的中序序列和左子树的前序序列递归构建左子树;
4. 根据右子树的中序序列和右子树的前序序列递归构建右子树;
5. 将左右子树连接到根节点上,返回该根节点。
具体实现可以参考下面的代码:
```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)
root_idx = inorder.index(root_val)
left_inorder = inorder[:root_idx]
right_inorder = inorder[root_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
# 测试代码
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
root = buildTree(preorder, inorder)
print(root.val) # 3
print(root.left.val) # 9
print(root.right.val) # 20
print(root.right.left.val) # 15
print(root.right.right.val) # 7
```