P 兄妹siblings题解问题背景与概述在算法竞赛和数据结构领域中“P 兄妹”问题通常被称为“Siblings”或“兄弟节点”是一个经典的树结构题目。该问题通常要求我们在一棵给定的树中找出所有具有相同父节点的节点对即兄弟节点或者计算某种与兄弟节点相关的统计量。虽然题目看似简单但其背后涉及了树的遍历、邻接表构建、哈希表映射等核心算法思想。本文将深入剖析该问题的原理并通过可运行的代码示例来展示两种不同的解法。## 问题定义与核心原理假设我们有一棵有根树节点编号从 0 到 N-1根节点为 0。每个节点可能有多个子节点。所谓“P 兄妹”即具有相同父节点的节点集合。例如如果父节点 A 有子节点 B、C、D那么 B、C、D 互为兄弟节点。核心原理在于兄弟节点的判定依赖于父节点信息。因此我们需要先建立每个节点到其父节点的映射关系或者直接通过遍历树来获取每个节点的子节点列表。一旦知道了每个节点的子节点集合那么集合中任意两个节点都是兄弟节点。常见的解法包括1.直接存储父节点数组通过输入构建 parent 数组然后按父节点分组。2.构建邻接表进行 DFS/BFS遍历树记录每个节点的子节点然后输出兄弟对。下面我们将通过具体代码来实现这些思路。## 解法一基于父节点数组的映射这种方法假设输入给出了每个节点的父节点编号根节点的父节点为 -1 或自身。我们可以利用字典哈希表将父节点映射到其子节点列表然后遍历字典输出兄弟节点。pythondef find_siblings_by_parent(parent): 根据父节点数组找出所有兄弟节点对 :param parent: list[int], 长度 Nparent[i] 表示节点 i 的父节点根节点父节点为 -1 :return: list[tuple], 每个元素为 (node1, node2) 的兄弟对 # 构建父节点到子节点列表的映射 from collections import defaultdict children_map defaultdict(list) for node, par in enumerate(parent): if par ! -1: # 忽略根节点的父节点 children_map[par].append(node) siblings_pairs [] # 遍历每个父节点的子节点列表 for par, children in children_map.items(): # 如果子节点数量大于等于2则所有两两组合都是兄弟对 for i in range(len(children)): for j in range(i1, len(children)): siblings_pairs.append((children[i], children[j])) return siblings_pairs# 示例树结构如下# 0# / \# 1 2# / \# 3 4parent [-1, 0, 0, 1, 1]result find_siblings_by_parent(parent)print(兄弟节点对, result) # 输出兄弟节点对[(1, 2), (3, 4)]代码解析-parent数组表示每个节点的父节点例如parent[2]0表示节点2的父节点是0。- 使用defaultdict(list)构建children_map键为父节点编号值为该父节点的所有子节点列表。- 对于每个父节点如果子节点数量大于等于2则使用两层循环生成所有组合对。- 最终返回所有兄弟节点对的列表。这种方法的时间复杂度为 O(N M)其中 N 是节点数M 是兄弟对的总数最坏情况下为 O(N^2)。空间复杂度为 O(N)。## 解法二基于树的DFS遍历如果输入是以邻接表形式给出的树我们可以通过 DFS 遍历来获取每个节点的子节点。这种方式更通用适合处理动态构建的树。pythondef find_siblings_by_dfs(adj, root0): 通过DFS遍历树找出所有兄弟节点对 :param adj: list[list[int]], 邻接表adj[i] 包含节点 i 的所有邻居 :param root: 根节点编号 :return: list[tuple], 兄弟节点对 from collections import defaultdict children_map defaultdict(list) visited set() def dfs(node, parent): visited.add(node) # 遍历邻居排除父节点即为子节点 for neighbor in adj[node]: if neighbor ! parent and neighbor not in visited: children_map[node].append(neighbor) dfs(neighbor, node) dfs(root, -1) siblings_pairs [] for par, children in children_map.items(): for i in range(len(children)): for j in range(i1, len(children)): siblings_pairs.append((children[i], children[j])) return siblings_pairs# 示例构建与上面相同的树结构邻接表形式# 节点0连接1,2节点1连接0,3,4节点2连接0节点3连接1节点4连接1adj [ [1, 2], # 节点0的邻居 [0, 3, 4], # 节点1的邻居 [0], # 节点2的邻居 [1], # 节点3的邻居 [1] # 节点4的邻居]result find_siblings_by_dfs(adj, root0)print(DFS找出的兄弟节点对, result) # 输出兄弟节点对[(1, 2), (3, 4)]代码解析-adj是邻接表每个元素是节点的邻居列表。注意树是无向图因此每个节点会存储所有邻居包括父节点。- DFS 函数dfs(node, parent)遍历树时将node的邻居中不是parent的节点视为子节点添加到children_map。- 由于树是无环的visited集合用于防止重复访问但在此处由于我们传入 parent 参数其实可以省略 visited但为了代码健壮性保留。- 最终同样生成兄弟节点对。这种方法的时间复杂度为 O(N M)空间复杂度为 O(N)递归栈空间和邻接表空间。## 进阶思考处理多叉树与性能优化在实际应用中树可能非常大兄弟节点对的数量可能呈指数级增长。例如如果一个父节点有 K 个子节点则其贡献的兄弟对数量为 C(K,2) K*(K-1)/2。如果所有节点都聚集在一个父节点下那么总兄弟对数量可达 O(N^2)。此时直接输出所有对可能导致内存溢出。优化策略包括-分批次处理如果只需统计兄弟对数量可以用公式直接计算无需生成所有对。-只输出前 K 个在算法竞赛中有时题目要求只输出按某种顺序排序的前几个兄弟对。-使用迭代器生成兄弟对时使用 yield 关键字实现惰性计算。例如以下代码演示了如何只统计兄弟对数量pythondef count_siblings(parent): from collections import Counter child_count Counter(parent) # 排除根节点父节点为-1 total_pairs 0 for par, cnt in child_count.items(): if par ! -1 and cnt 2: total_pairs cnt * (cnt - 1) // 2 return total_pairsparent [-1, 0, 0, 1, 1]print(兄弟对数量, count_siblings(parent)) # 输出2## 总结“P 兄妹”问题是一个典型的树结构应用其核心在于通过父节点信息或遍历树来识别兄弟关系。本文介绍了两种主要解法基于父节点数组的映射法和基于DFS遍历的邻接表法并提供了可直接运行的Python代码示例。两种方法的时间复杂度均为 O(N M)空间复杂度为 O(N)。在实际工程中应根据输入数据的格式父节点数组还是邻接表选择合适的方法。此外当兄弟对数量极大时需要注意内存和性能优化例如采用公式计算数量或惰性输出。通过本题的剖析读者可以加深对树遍历、哈希表映射以及组合数学的理解这些技巧在更复杂的树形结构问题如最近公共祖先、子树查询等中同样适用。