根据先序遍历序列和中序遍历序列构建二叉树代码
时间: 2023-11-20 07:07:00 浏览: 81
以下是根据先序遍历序列和中序遍历序列构建二叉树的代码实现(Python 3):
```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)
root.left = buildTree(preorder[1:root_index+1], inorder[:root_index])
root.right = buildTree(preorder[root_index+1:], inorder[root_index+1:])
return root
```
其中,TreeNode 表示二叉树的节点,buildTree 函数接受先序遍历序列和中序遍历序列作为参数,并返回构建出的二叉树的根节点。在函数内部,首先判断先序遍历序列和中序遍历序列是否为空,如果有一个为空,则返回 None。然后,取出先序遍历序列的第一个元素作为根节点的值 root_val,并创建根节点 root。接着,找到 root_val 在中序遍历序列中的位置 root_index,并根据 root_index 将中序遍历序列分为左子树部分和右子树部分。然后,分别递归构建左子树和右子树,并将其作为根节点的左右子节点。最后,返回根节点即可。
阅读全文