给出一颗二叉树的先序遍历和中序遍历,要求你输出这棵二叉树的层次遍历。并给出代码实现
时间: 2023-04-09 16:03:16 浏览: 53
可以回答这个问题。以下是代码实现:
```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:1+root_index], inorder[:root_index])
root.right = buildTree(preorder[1+root_index:], inorder[root_index+1:])
return root
def levelOrder(root):
if not root:
return []
queue = [root]
res = []
while queue:
level = []
for _ in range(len(queue)):
node = queue.pop(0)
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level)
return res
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
root = buildTree(preorder, inorder)
print(levelOrder(root))
```
输出结果为:
```
[[3], [9, 20], [15, 7]]
```