已知二叉树的先序序列,输出层序遍历序列。 输入格式: 输入在一行中给出二叉树的先序序列。*表示空格 输出格式: 输出共一行,是二叉树的层序遍历序列。
时间: 2024-06-13 22:04:35 浏览: 19
根据二叉树的层序遍历的特点,我们可以使用队列来实现。先将根节点入队,然后每次从队列中取出一个节点,将其左右子节点入队,直到队列为空。这样就可以按照层序遍历的顺序输出二叉树的节点值。
具体实现步骤如下:
1. 读入先序序列,建立二叉树。
2. 将根节点入队。
3. 当队列不为空时,取出队首节点,输出其值,并将其左右子节点入队。
4. 重复步骤3,直到队列为空。
代码如下:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def buildTree(preorder):
if not preorder:
return None
val = preorder.pop(0)
if val == '*':
return None
root = TreeNode(int(val))
root.left = buildTree(preorder)
root.right = buildTree(preorder)
return root
def levelOrder(root):
if not root:
return []
queue = [root]
res = []
while queue:
node = queue.pop(0)
res.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return res
preorder = input().split()
root = buildTree(preorder)
res = levelOrder(root)
print(' '.join(map(str, res)))
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)