LeetCode 题解工作台
重构一棵树的方案数
给你一个数组 pairs ，其中 pairs[i] = [x i , y i ] ，并且满足： pairs 中没有重复元素 x i i 令 ways 为满足下面条件的有根树的方案数： 树所包含的所有节点值都在 pairs 中。 一个数对 [x i , y i ] 出现在 pairs 中 当且仅当 x…
2
题型
4
代码语言
3
相关题
当前训练重点
困难 · 二分·树·traversal
答案摘要
class Solution: def checkWays(self, pairs: List[List[int]]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一个数组 pairs ，其中 pairs[i] = [xi, yi] ，并且满足：
pairs中没有重复元素xi < yi
令 ways 为满足下面条件的有根树的方案数：
- 树所包含的所有节点值都在
pairs中。 - 一个数对
[xi, yi]出现在pairs中 当且仅当xi是yi的祖先或者yi是xi的祖先。 - 注意：构造出来的树不一定是二叉树。
两棵树被视为不同的方案当存在至少一个节点在两棵树中有不同的父节点。
请你返回：
- 如果
ways == 0，返回0。 - 如果
ways == 1，返回1。 - 如果
ways > 1，返回2。
一棵 有根树 指的是只有一个根节点的树，所有边都是从根往外的方向。
我们称从根到一个节点路径上的任意一个节点（除去节点本身）都是该节点的 祖先 。根节点没有祖先。
示例 1：
输入：pairs = [[1,2],[2,3]] 输出：1 解释：如上图所示，有且只有一个符合规定的有根树。
示例 2：
输入：pairs = [[1,2],[2,3],[1,3]] 输出：2 解释：有多个符合规定的有根树，其中三个如上图所示。
示例 3：
输入：pairs = [[1,2],[2,3],[2,4],[1,5]] 输出：0 解释：没有符合规定的有根树。
提示：
1 <= pairs.length <= 1051 <= xi < yi <= 500pairs中的元素互不相同。
解题思路
方法一
class Solution:
def checkWays(self, pairs: List[List[int]]) -> int:
g = [[False] * 510 for _ in range(510)]
v = defaultdict(list)
for x, y in pairs:
g[x][y] = g[y][x] = True
v[x].append(y)
v[y].append(x)
nodes = []
for i in range(510):
if v[i]:
nodes.append(i)
g[i][i] = True
nodes.sort(key=lambda x: len(v[x]))
equal = False
root = 0
for i, x in enumerate(nodes):
j = i + 1
while j < len(nodes) and not g[x][nodes[j]]:
j += 1
if j < len(nodes):
y = nodes[j]
if len(v[x]) == len(v[y]):
equal = True
for z in v[x]:
if not g[y][z]:
return 0
else:
root += 1
if root > 1:
return 0
return 2 if equal else 1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | and space complexity depend on building adjacency maps and traversing all nodes, typically O(N + E), where N is the number of nodes and E is the number of pairs, but state tracking adds additional overhead in worst cases. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Looks for correct identification of the root node across all pairs.
- question_mark
Watches for proper handling of multiple valid reconstructions using state tracking.
- question_mark
Checks whether the traversal maintains consistent parent-child relationships across the tree.
常见陷阱
外企场景- error
Assuming any node with highest degree is root without verifying it connects to all others.
- error
Failing to track multiple valid parent candidates, missing multiple reconstructions.
- error
Overlooking conflicts in adjacency that make a tree impossible, returning incorrect counts.
进阶变体
外企场景- arrow_right_alt
Counting reconstructions for a tree with weighted edges.
- arrow_right_alt
Handling disconnected node pairs that cannot form a single rooted tree.
- arrow_right_alt
Extending to allow n-ary trees instead of strictly binary traversal.