python 对于给定的二叉树,本题要求你按从上到下、从左到右的顺序输出其所有叶节点。 输入格式: 首先第一行给出一个正整数 N(≤10),为树中结点总数。树中的结点从 0 到 N−1 编号。随后 N 行,每行给出一个对应结点左右孩子的编号。如果某个孩子不存在,则在对应位置给出 "-"。编号间以 1 个空格分隔。 输出格式: 在一行中按规定顺序输出叶节点的编号。编号间以 1 个空格分隔,行首尾不得有多余空格
时间: 2024-02-13 15:07:11 浏览: 25
同样的问题,这里提供一种使用二叉树的层序遍历算法(BFS)的解法,具体思路是借助队列来实现,从根节点开始,依次将每层的非空节点入队,并将它们的左右子节点入队,直到队列为空。对于每个节点,如果左右子节点都为空,则该节点是叶子节点,将其编号记录下来。最后输出所有叶子节点的编号即可。具体实现可以参考下面的 Python 代码:
```python
# 定义树节点
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 二叉树的层序遍历
def bfs(root):
q = [root]
leaf_nodes = []
while q:
n = len(q)
for i in range(n):
node = q.pop(0)
# 如果该节点是叶子节点,则将其编号记录下来
if not node.left and not node.right:
leaf_nodes.append(node.val)
# 将左右孩子节点加入队列
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return leaf_nodes
# 主函数
if __name__ == '__main__':
n = int(input())
nodes = [None] * n
for i in range(n):
left, right = input().split()
if left != '-':
left = int(left)
if not nodes[left]:
nodes[left] = TreeNode(left)
nodes[i].left = nodes[left]
if right != '-':
right = int(right)
if not nodes[right]:
nodes[right] = TreeNode(right)
nodes[i].right = nodes[right]
root = nodes[0]
leaf_nodes = bfs(root)
print(' '.join(str(x) for x in leaf_nodes))
```
输入样例:
```
8
1 - - - 0 - 2 7 - - - - 5 - 4 6
```
输出样例:
```
4 1 5
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![py](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)