由二叉树的先序遍历和中序遍历序列构建二叉树的二叉链表
时间: 2023-11-22 15:04:33 浏览: 98
可以使用递归方法来实现构建二叉树。具体实现过程可以参考以下代码:
```python
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def buildTree(preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
i = inorder.index(root_val)
root.left = buildTree(preorder[1:i+1], inorder[:i])
root.right = buildTree(preorder[i+1:], inorder[i+1:])
return root
```
其中,preorder和inorder分别为二叉树的先序遍历和中序遍历序列。在该代码中,首先我们取preorder的第一个元素为root_val,创建一个值为root_val的新节点root。然后,在中序遍历序列inorder中查找root_val,并将inorder分成左右两个部分。左部分的所有元素为root节点的左子树的中序遍历序列,右部分的所有元素为root节点的右子树的中序遍历序列。在先序遍历序列preorder中,前i+1个元素为root节点的左子树的先序遍历序列,后面的元素为root节点的右子树的先序遍历序列。我们可以通过递归调用buildTree函数来构建子树,最终返回构建好的二叉树的根节点。
阅读全文