根据前序遍历和中序遍历建立二叉树
时间: 2023-11-26 16:44:19 浏览: 32
好的,根据前序遍历和中序遍历建立二叉树的具体步骤如下:
1. 根据前序遍历确定根节点。
2. 在中序遍历中找到根节点的位置,根节点左边的部分为左子树,右边的部分为右子树。
3. 根据左子树的前序遍历和中序遍历递归建立左子树。
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)
root.left = buildTree(preorder[1:root_index+1], inorder[:root_index])
root.right = buildTree(preorder[root_index+1:], inorder[root_index+1:])
return root
```
其中,`preorder` 和 `inorder` 分别为前序遍历和中序遍历的列表。