class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass Solution: def pruneLeaves(self, root: TreeNode) -> TreeNode: if not root: return None # 字典存储每个节点的深度 depth = {} # 第一次DFS：计算每个节点的深度 def compute_depth(node): if node is None: return float('inf') # 空节点返回极大值 left_depth = compute_depth(node.left) right_depth = compute_depth(node.right) # 如果两边都是空，返回0（叶子节点） if left_depth == float('inf') and right_depth == float('inf'): depth[node] = 0 return 0 # 计算当前节点深度 current_depth = min(left_depth, right_depth) + 1 depth[node] = current_depth return current_depth compute_depth(root) # 第二次DFS：移除深度为1的节点 def remove_nodes(node): if node is None: return None # 如果当前节点深度为1，移除整个子树 if depth.get(node, float('inf')) == 1: return None # 递归处理左右子树 node.left = remove_nodes(node.left) node.right = remove_nodes(node.right) return node return remove_nodes(root)def build_tree(s: str) -> TreeNode: """构建二叉树，处理输入格式{1,#,1,#,1,#,1,#,1}""" s = s.strip('{}') if not s: return None items = s.split(',') if not items or items[0] == '': return None # 处理节点值 nodes = for item in items: item = item.strip if item == '#': nodes.append(None) else: nodes.append(int(item)) if not nodes or nodes[0] is None: return None root = TreeNode(nodes[0]) queue = [root] i = 1 while queue and i str: """二叉树转为{1,#,1,#,1}格式字符串""" if not root: return "{}" result = queue = [root] while queue: node = queue.pop(0) if node: result.append(str(node.val)) queue.append(node.left) queue.append(node.right) else: result.append('#') # 去除尾部多余的# while result and result[-1] == '#': result.pop return '{' + ','.join(result) + '}'def main: # 读取一行输入 line = input.strip if not line: print("{}") return # 构建二叉树 root = build_tree(line) if not root: print("{}") return # 修剪二叉树 pruned_root = Solution.pruneLeaves(root) # 转换为字符串并输出 output = tree_to_string(pruned_root) print(output)if __name__ == "__main__": main摘要：class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass Solution
来源：小乐课堂
