用前序中序后续遍历方法创建一棵二叉树。
时间: 2024-05-11 22:18:49 浏览: 6
首先,我们需要了解前序遍历、中序遍历和后序遍历的定义:
- 前序遍历:先访问根节点,再遍历左子树,最后遍历右子树。
- 中序遍历:先遍历左子树,再访问根节点,最后遍历右子树。
- 后序遍历:先遍历左子树,再遍历右子树,最后访问根节点。
我们以前序遍历和中序遍历来构建一棵二叉树。假设前序遍历序列为[3,9,20,15,7],中序遍历序列为[9,3,15,20,7]。
我们可以按照以下步骤进行构建:
1. 前序遍历序列的第一个元素3是根节点。
2. 在中序遍历序列中找到根节点3的位置,可以将中序遍历序列分成左子树[9]和右子树[15,20,7]。
3. 在前序遍历序列中,根节点之后的3个元素[9,20,15]属于左子树,剩下的1个元素[7]属于右子树。
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 = TreeNode(preorder[0])
# 在中序遍历序列中找到根节点位置
idx = inorder.index(preorder[0])
# 递归地构建左子树和右子树
root.left = buildTree(preorder[1:idx+1], inorder[:idx])
root.right = buildTree(preorder[idx+1:], inorder[idx+1:])
return root
# 测试代码
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
root = buildTree(preorder, inorder)
```
通过以上代码,我们成功地创建了一棵二叉树。