本关任务要求采用前序遍历序列和中序遍历序列构造二叉树。
时间: 2023-12-30 10:04:33 浏览: 107
以下是构造二叉树的步骤:
1. 从前序遍历序列中取出第一个元素作为根节点。
2. 在中序遍历序列中找到根节点的位置,将中序遍历序列分为左子树和右子树两部分。
3. 根据左子树和右子树的长度,在前序遍历序列中分别找到左子树和右子树的元素。
4. 递归地构造左子树和右子树,并将它们分别作为根节点的左右子节点。
下面是一个示例代码,以树 3 / \ 9 20 / / \ 8 15 7 / \ 5 10 / 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)
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 = buildTree(left_preorder, left_inorder)
root.right = buildTree(right_preorder, right_inorder)
return root
preorder = [3, 9, 8, 5, 4, 10, 20, 15, 7]
inorder = [4, 5, 8, 10, 9, 3, 15, 20, 7]
root = buildTree(preorder, inorder)
```
阅读全文