给定一棵二叉树的前序遍历序列和中序遍历序列可以构造出这棵二叉树。例如前序序列是ABDECFG,中序序列是DBEAFCG,那么这颗二叉树的结构的代码
时间: 2023-08-10 12:31:41 浏览: 147
好的,以下是根据前序遍历序列和中序遍历序列构造二叉树的代码实现(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)
index = inorder.index(root_val)
root.left = buildTree(preorder[1:index+1], inorder[:index])
root.right = buildTree(preorder[index+1:], inorder[index+1:])
return root
# 测试代码
preorder = ['A', 'B', 'D', 'E', 'C', 'F', 'G']
inorder = ['D', 'B', 'E', 'A', 'F', 'C', 'G']
root = buildTree(preorder, inorder)
```
在上述代码中,我们首先定义了一个二叉树节点的类 TreeNode,包含值 val 和左右子节点 left 和 right。然后,我们定义了一个函数 buildTree,它接受两个参数,分别是前序遍历序列 preorder 和中序遍历序列 inorder。函数的返回值为根节点 root。在函数中,我们首先检查 preorder 和 inorder 是否为空,若其中任意一个为空,则返回 None。接着,我们从 preorder 中取出根节点的值 root_val,并创建一个节点 root。然后,我们在 inorder 中查找 root_val 的位置 index,从而得到左子树的中序遍历序列 inorder[:index] 和右子树的中序遍历序列 inorder[index+1:]。接着,我们递归地构建 root 的左右子树,其前序遍历序列分别为 preorder[1:index+1] 和 preorder[index+1:],然后将其作为 root 的左右子节点。最后,返回根节点 root。
我们可以通过调用 buildTree 函数,并将前序遍历序列和中序遍历序列作为参数来构造一棵二叉树。在上述代码中,我们给出了题目中所给的前序遍历序列 preorder 和中序遍历序列 inorder 的示例,可以通过调用 buildTree(preorder, inorder) 来构造一棵二叉树。最终得到的二叉树的结构如下:
```
A
/ \
B C
/ \ \
D E F
/ \
G H
```
阅读全文