Python 利用 BFS 统计非空二叉树每层度为 1 结点数目

要解决这个问题，我们可以使用广度优先搜索（BFS）来遍历二叉树的每一层，并在遍历过程中统计每层度为1的节点数目。度为1的节点指的是只有一个子节点的节点。 代码实现 ```python from collections import deque class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def build_tree(s): if not s: return None stack = [] root = TreeNode(s[0]) stack.append(root) idx = 1 while stack and idx < len(s): node = stack.pop() if s[idx] != '#': node.left = TreeNode(s[idx]) stack.append(node.left) idx += 1 if idx < len(s) and s[idx] != '#': node.right = TreeNode(s[idx]) stack.append(node.right) idx += 1 return root def count_degree_one_nodes(root): if not root: return [] queue = deque([root]) result = [] while queue: level_size = len(queue) count = 0 for _ in range(level_size): node = queue.popleft() if (node.left and not node.right) or (not node.left and node.right): count += 1 if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(count) return result # 输入处理 s = input().strip() root = build_tree(s) result = count_degree_one_nodes(root) # 输出结果 for count in result: print(count) ``` 代码解释 1. TreeNode类：定义了二叉树的节点结构，每个节点包含一个值`val`，以及左右子节点`left`和`right`。 2. build_tree函数：根据输入的字符串构建二叉树。使用栈来辅助构建树结构，遇到`#`表示空节点。 3. count_degree_one_nodes函数：使用BFS遍历二叉树的每一层，统计每层度为1的节点数目。度为1的节点是指只有一个子节点的节点。 4. 输入处理：读取输入的字符串，调用`build_tree`函数构建二叉树。 5. 输出结果：遍历`result`列表，输出每层度为1的节点数目。 额外需要注意的逻辑点 - 输入的字符串可能包含空节点（`#`），需要在构建树时正确处理。 - 使用BFS遍历时，需要确保每层的节点数目统计准确。 - 度为1的节点包括只有左子节点或只有右子节点的情况。 ######[AI写代码神器 | 580点数解答 | 2025-03-19 11:29:04]