已知层次遍历和中序遍历序列 构造二叉树
时间: 2023-06-22 19:49:02 浏览: 145
二叉树 给两个序列输出另外一个序列
可以根据已知的层次遍历和中序遍历序列构造二叉树的步骤如下:
1. 从层次遍历序列中找到根节点,并将其作为二叉树的根节点。
2. 在中序遍历序列中找到根节点的位置,将中序遍历序列分成左子树和右子树两个部分。
3. 根据左子树和右子树的中序遍历序列长度,将层次遍历序列分成左子树和右子树两个部分。
4. 递归地对左子树和右子树进行步骤1-3,分别构造出左子树和右子树。
5. 将左子树和右子树分别作为根节点的左子树和右子树。
具体实现可以参考以下的 Python 代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(levelorder, inorder):
if not levelorder or not inorder:
return None
# 找到根节点
root_val = levelorder[0]
root_index = inorder.index(root_val)
root = TreeNode(root_val)
# 构造左子树和右子树
left_inorder = inorder[:root_index]
right_inorder = inorder[root_index+1:]
left_levelorder = [x for x in levelorder if x in left_inorder]
right_levelorder = [x for x in levelorder if x in right_inorder]
root.left = buildTree(left_levelorder, left_inorder)
root.right = buildTree(right_levelorder, right_inorder)
return root
```
其中,`levelorder` 表示层次遍历序列,`inorder` 表示中序遍历序列。函数返回构造出的二叉树的根节点。
阅读全文