树中两个距离相等的点
Two equally distant points in a tree
我正在解决 Python 中的试用期示例问题，到目前为止只取得了部分成功（通过了 30 个测试用例，第 31 个是错误答案）。测试用例本身没有公开。
说明。
给出了一个由 n-1 个链接连接的 n 个节点组成的网络。找到两个节点，使得从最父亲节点到这两个节点中最近节点的距离最小。如果可能有多个答案，将接受其中任何一个。
输入以数字对列表的形式给出。每个数字代表节点，pair是两个节点之间的连接。结果应该是两个节点的列表。
示例 1
在 = [[1, 2], [2, 3]]
结果 = [3, 1]
示例 2
在 = [[1, 2], [3, 2], [2, 4], [4, 5], [4, 6]]
结果 = [2, 4]
我的解决方案。
网络永远是树，而不是图。对于上述示例，相应的树将是：
示例 1
1-2-3
示例 2
1 5
\ /
2-4
/ \
3 6
我的解决方案基于逐步从叶子到中间，最终从叶子中移除节点——一层接一层。最后我会在中间有一个或两个节点。
示例 A.
1-2-3 8-9-10-14 2-3 8-9-10 3 8-9
\ / \ / \ /
7 >>> 7 >>> 7 >>> 7-8
/ \ / \ / \
4-5-6 11-12-13 5-6 11-12 6 11
结果：[7, 8]
示例 B.
1-2-3 8-9-10 2-3 8-9 3 8
\ / \ / \ /
7 >>> 7 >>> 7 >>> 7
/ \ / \ / \
4-5-6 11-12-13 5-6 11-12 6 11
结果：[7, ...]
示例 C.
11 13
\ /
1-2-3-4-5-6-7-8-9-10 >> ... >> 3-4-5-6-7-8 >> ... >> 5-6
/ \
12 14
结果：[3, 8]
如果除了最后一步（示例 B）之外，每一步之后我们有两个以上的节点，那么答案将是单个中间节点和任何其他节点。
至于其他情况，如果我们到中点有n步，并且在n步到中心的一半后有两端（示例C），那么两端将是等距的从原始树的末端和它的中间（如果线段长度是偶数，两个中间是可能的）。这两端将是答案。如果我们在 n 步的一半后仍然没有两端（示例 A），那么我们将继续向中间移动，一旦端数将缩小到两个，两端就是答案。
可能上面的推理有漏洞，此时已经有人注意到了。
现在开始实施。
我将树表示为字典。键是代表节点的数字，值是代表邻居节点的数字集。从一棵树上移除端点相当于移除只有一个邻居的键并从其所有父节点中移除相应的数字。
下面是原始树表示及其对 示例 A 的第一次修改。
{1: {2},
2: {1, 3},
3: {2, 7},
4: {5},
5: {4, 6},
6: {5, 7},
7: {3, 6, 8, 11},
8: {7, 9},
9: {8, 10},
10: {9, 14},
11: {7, 12},
12: {11, 13},
13: {12},
14: {10}}
{2: {3},
3: {2, 7},
5: {6},
6: {5, 7},
7: {3, 6, 8, 11},
8: {7, 9},
9: {8, 10},
10: {9},
11: {7, 12},
12: {11}}
实现本身。
def f(pairs):
if len(pairs) == 1:
return pairs[0]
tree = {}
for a, b in pairs:
if a not in tree:
tree[a] = set()
if b not in tree:
tree[b] = set()
tree[a].add(b)
tree[b].add(a)
ends = {e for e in tree if len(tree[e]) == 1}
slices = [ends.copy()]
while len(tree.keys()) > 2:
nx_ends = set()
for end in ends:
pars = tree.pop(end, set())
nx_ends.update(pars)
for par in pars:
tree[par].remove(end)
nx_ends = {e for e in nx_ends if len(tree[e]) < 2}
ends = nx_ends.copy()
if ends:
slices.append(ends)
steps = len(slices) // 2
for ends in slices[steps:]:
ends = list(ends)
if len(ends) == 2:
return ends
if len(ends) == 1:
end = ends[0]
for el in pairs[0]:
if el != end:
return [end, el]
我的解决方案似乎相当有效，但再次在（不幸关闭）第 31 个测试用例中给出错误答案。
更新
我已经完成任务了。该解决方案基于上述解决方案并添加了一些额外的步骤。
在我——根据之前的算法——从较长的一端找到两个候选点后，我做了额外的检查——它们是否真的等距。如果从两个候选点覆盖所有节点的步数大于从较长端到达两个候选点的步数，则执行额外的向中心移动。
shift的值是步长差的一半，因为每一步到中心不仅增加到长端的距离，而且减少到另一端的距离。
def get_slices(slic, dic, from_ends=False):
visited = slic.copy()
slices = []
while slic:
slices.append(slic.copy())
nx_slice = set()
for end in slic:
neibs = dic[end]
for neib in neibs:
if neib not in visited:
nx_slice.add(neib)
if from_ends:
nx_slice = {e for e in nx_slice if len(dic[e] - visited) < 2}
slic = nx_slice
visited.update(slic)
return slices
def get_pair(node, pairs):
for pair in pairs:
if node in pair:
return pair
def f(pairs):
dic = {}
if len(pairs) == 1:
return pairs[0]
for a, b in pairs:
if a not in dic:
dic[a] = set()
if b not in dic:
dic[b] = set()
dic[a].add(b)
dic[b].add(a)
ends = {e for e in dic if len(dic[e]) == 1}
slices = get_slices(ends, dic, from_ends=True)
steps = len(slices) // 2
slices = slices[steps:]
while len(slices[0]) > 2:
slices.pop(0)
steps += 1
slic = slices.pop(0)
slices_center = get_slices(slic, dic)
steps_center = len(slices_center) - 1
slices_center.clear()
diff = steps_center - steps
if diff > 1:
slic = slices[diff // 2 - 1]
if len(slic) == 1:
[r] = slic
return get_pair(r, pairs)
return slic
我现在的问题是我的解决方案是否过于复杂？你能给个更简单的提示吗？
我在我的实现中发现了基本的算法错误，可以用一个例子来证明它。
52
|
53
|
24-23-22-1-2-3-4-33-32-31-42-43-44
按照我的算法最终切完后修改如下
53
|
23-22-1-2-3-4-33-32-31-42-43
22-1-2-3-4-33-32-31-42
1-2-3-4-33-32-31
24-23-22-1-2-3-4和4-33-32-31-42-43-44段的中心节点分别为1和31，将它们作为答案.然而，节点 52 离他们太远了。
正确答案是节点 2 和 32。如果您查看原始树，您会很容易注意到它们与节点 24、44 和 52 等距，距离等于 4。
我找到了我更满意的解决方案，据说更接近问题创建者的意图。该解决方案涉及 tree hight-balancing 和 reparenting 等概念。不幸的是，和以前一样，它包含一些细微的错误，在后一种关闭的情况下显示为运行时异常。
算法如下。
首先让我们假设某个任意节点是根。然后我们检查每个分支深度并找到更长的分支。之后我们完成重父化：我们将根更改为分支更高的节点，树的其余部分将成为新树的分支。
以这种方式，我们继续重新设置父级，直到我们到达相同长度的分支或深度相差一个节点的分支。此时我们将树视为高度平衡。
然后我们将（其中一个）较长的分支视为一棵单独的树，将原始树的其余部分视为另一棵单独的树，并通过最终重新设置父级再次平衡这两棵树。那些平衡树的根就是答案。
我们举个例子。假设我们有下面这棵树。
52
|
53
|
24-23-22-01-02-03-04-33-32-31-42-43-44
假设根是23个节点。所以我们最终要重生。
24
| 23
23 |__
| | |
22 22 24
| |
01 01
| |
02 02
| |
03 03
| |
04 04 04
|__ >> |__ >> … >> |_____
| | | | | | |
33 53 33 53 33 03 53
| | | | | | |
32 52 32 52 32 02 52
| | | |
31 31 31 01
| | | |
42 42 42 22
| | | |
43 43 43 23
| | | |
44 44 44 24
然后我们将最长的分支之一（33-32-31-42-43-44）视为一棵树，将树的其余部分视为另一棵树。
04
|__
| |
03 53 33
| | |
02 52 … 32
| |
01 31
| |
22 42
| |
23 43
| |
24 44
然后，我们依次平衡这两棵树。平衡后它们将如下。
02
|__
| | 31
01 03 |__
| | | |
22 04 42 32
| | | |
23 53 43 33
| | |
24 52 44
所以答案将是节点 02 和 31。
为了使实现足够有效，我们需要为每个节点兑现树深度。这样我们就不需要在每次重新设置父级后重新计算所有深度——每次重新设置父级后只需重新计算新根和一个新分支的深度就足够了。
所以，这里是实现。
class Node:
def __init__(self, val):
self.val = val
self.children = []
def construct_tree(pairs):
pairs = [tuple(list(sorted(pair))) for pair in pairs]
pairs.sort(reverse=True)
p, c = pairs.pop()
root = Node(p)
child = Node(c)
root.children.append(child)
nodes_dic = {p: root, c: child}
while pairs:
pair = pairs.pop()
p, c = pair
if c in nodes_dic:
p, c = c, p
if p in nodes_dic:
parent = nodes_dic[p]
node = Node(c)
parent.children.append(node)
nodes_dic[c] = node
else:
pairs.insert(0, pair)
return root
def get_depth(node, depths):
if node.val not in depths:
if not node.children:
depths[node.val] = 0
else:
depths[node.val] = 1 + max([get_depth(child, depths) for child in node.children])
return depths[node.val]
def reparent_tree(root, new_root, depths):
children = [child for child in root.children if child != new_root]
val = root.val
if val in depths:
del depths[val]
if new_root.val in depths:
del depths[new_root.val]
root = new_root
child = Node(val)
child.children = children
root.children.append(child)
return root
def balance_tree(root):
depths = {}
if len(root.children) == 0:
return root, None
if len(root.children) == 1:
root = reparent_tree(root, root.children[0], depths)
if get_depth(root, depths) < 2:
return root, root.children[0]
while True:
ls = [get_depth(node, depths) for node in root.children]
l1, l2 = list(sorted(ls))[-2:]
ind = ls.index(l2)
candidate_root = root.children[ind]
if l2 - l1 <= 1:
break
root = reparent_tree(root, candidate_root, depths)
return root, candidate_root
def f(pairs):
if len(pairs) <= 2:
return pairs[0]
root = construct_tree(pairs)
root, tree1 = balance_tree(root)
root.children.remove(tree1)
tree2 = root
tree1, _ = balance_tree(tree1)
tree2, _ = balance_tree(tree2)
return tree1.val, tree2.val
解决方案通过了我的测试用例——手工制作的和一些随机生成的，没有运行时错误，很难找出问题所在。
我正在解决 Python 中的试用期示例问题，到目前为止只取得了部分成功（通过了 30 个测试用例，第 31 个是错误答案）。测试用例本身没有公开。
说明。
给出了一个由 n-1 个链接连接的 n 个节点组成的网络。找到两个节点，使得从最父亲节点到这两个节点中最近节点的距离最小。如果可能有多个答案，将接受其中任何一个。
输入以数字对列表的形式给出。每个数字代表节点，pair是两个节点之间的连接。结果应该是两个节点的列表。
示例 1 在 = [[1, 2], [2, 3]] 结果 = [3, 1]
示例 2 在 = [[1, 2], [3, 2], [2, 4], [4, 5], [4, 6]] 结果 = [2, 4]
我的解决方案。
网络永远是树，而不是图。对于上述示例，相应的树将是：
示例 1
1-2-3
示例 2
1 5
\ /
2-4
/ \
3 6
我的解决方案基于逐步从叶子到中间，最终从叶子中移除节点——一层接一层。最后我会在中间有一个或两个节点。
示例 A.
1-2-3 8-9-10-14 2-3 8-9-10 3 8-9
\ / \ / \ /
7 >>> 7 >>> 7 >>> 7-8
/ \ / \ / \
4-5-6 11-12-13 5-6 11-12 6 11
结果：[7, 8]
示例 B.
1-2-3 8-9-10 2-3 8-9 3 8
\ / \ / \ /
7 >>> 7 >>> 7 >>> 7
/ \ / \ / \
4-5-6 11-12-13 5-6 11-12 6 11
结果：[7, ...]
示例 C.
11 13
\ /
1-2-3-4-5-6-7-8-9-10 >> ... >> 3-4-5-6-7-8 >> ... >> 5-6
/ \
12 14
结果：[3, 8]
如果除了最后一步（示例 B）之外，每一步之后我们有两个以上的节点，那么答案将是单个中间节点和任何其他节点。 至于其他情况，如果我们到中点有n步，并且在n步到中心的一半后有两端（示例C），那么两端将是等距的从原始树的末端和它的中间（如果线段长度是偶数，两个中间是可能的）。这两端将是答案。如果我们在 n 步的一半后仍然没有两端（示例 A），那么我们将继续向中间移动，一旦端数将缩小到两个，两端就是答案。
可能上面的推理有漏洞，此时已经有人注意到了。
现在开始实施。 我将树表示为字典。键是代表节点的数字，值是代表邻居节点的数字集。从一棵树上移除端点相当于移除只有一个邻居的键并从其所有父节点中移除相应的数字。
下面是原始树表示及其对 示例 A 的第一次修改。
{1: {2},
2: {1, 3},
3: {2, 7},
4: {5},
5: {4, 6},
6: {5, 7},
7: {3, 6, 8, 11},
8: {7, 9},
9: {8, 10},
10: {9, 14},
11: {7, 12},
12: {11, 13},
13: {12},
14: {10}}
{2: {3},
3: {2, 7},
5: {6},
6: {5, 7},
7: {3, 6, 8, 11},
8: {7, 9},
9: {8, 10},
10: {9},
11: {7, 12},
12: {11}}
实现本身。
def f(pairs):
if len(pairs) == 1:
return pairs[0]
tree = {}
for a, b in pairs:
if a not in tree:
tree[a] = set()
if b not in tree:
tree[b] = set()
tree[a].add(b)
tree[b].add(a)
ends = {e for e in tree if len(tree[e]) == 1}
slices = [ends.copy()]
while len(tree.keys()) > 2:
nx_ends = set()
for end in ends:
pars = tree.pop(end, set())
nx_ends.update(pars)
for par in pars:
tree[par].remove(end)
nx_ends = {e for e in nx_ends if len(tree[e]) < 2}
ends = nx_ends.copy()
if ends:
slices.append(ends)
steps = len(slices) // 2
for ends in slices[steps:]:
ends = list(ends)
if len(ends) == 2:
return ends
if len(ends) == 1:
end = ends[0]
for el in pairs[0]:
if el != end:
return [end, el]
我的解决方案似乎相当有效，但再次在（不幸关闭）第 31 个测试用例中给出错误答案。
更新
我已经完成任务了。该解决方案基于上述解决方案并添加了一些额外的步骤。
在我——根据之前的算法——从较长的一端找到两个候选点后，我做了额外的检查——它们是否真的等距。如果从两个候选点覆盖所有节点的步数大于从较长端到达两个候选点的步数，则执行额外的向中心移动。
shift的值是步长差的一半，因为每一步到中心不仅增加到长端的距离，而且减少到另一端的距离。
def get_slices(slic, dic, from_ends=False):
visited = slic.copy()
slices = []
while slic:
slices.append(slic.copy())
nx_slice = set()
for end in slic:
neibs = dic[end]
for neib in neibs:
if neib not in visited:
nx_slice.add(neib)
if from_ends:
nx_slice = {e for e in nx_slice if len(dic[e] - visited) < 2}
slic = nx_slice
visited.update(slic)
return slices
def get_pair(node, pairs):
for pair in pairs:
if node in pair:
return pair
def f(pairs):
dic = {}
if len(pairs) == 1:
return pairs[0]
for a, b in pairs:
if a not in dic:
dic[a] = set()
if b not in dic:
dic[b] = set()
dic[a].add(b)
dic[b].add(a)
ends = {e for e in dic if len(dic[e]) == 1}
slices = get_slices(ends, dic, from_ends=True)
steps = len(slices) // 2
slices = slices[steps:]
while len(slices[0]) > 2:
slices.pop(0)
steps += 1
slic = slices.pop(0)
slices_center = get_slices(slic, dic)
steps_center = len(slices_center) - 1
slices_center.clear()
diff = steps_center - steps
if diff > 1:
slic = slices[diff // 2 - 1]
if len(slic) == 1:
[r] = slic
return get_pair(r, pairs)
return slic
我现在的问题是我的解决方案是否过于复杂？你能给个更简单的提示吗？
我在我的实现中发现了基本的算法错误，可以用一个例子来证明它。
52
|
53
|
24-23-22-1-2-3-4-33-32-31-42-43-44
按照我的算法最终切完后修改如下
53
|
23-22-1-2-3-4-33-32-31-42-43
22-1-2-3-4-33-32-31-42
1-2-3-4-33-32-31
24-23-22-1-2-3-4和4-33-32-31-42-43-44段的中心节点分别为1和31，将它们作为答案.然而，节点 52 离他们太远了。 正确答案是节点 2 和 32。如果您查看原始树，您会很容易注意到它们与节点 24、44 和 52 等距，距离等于 4。
我找到了我更满意的解决方案，据说更接近问题创建者的意图。该解决方案涉及 tree hight-balancing 和 reparenting 等概念。不幸的是，和以前一样，它包含一些细微的错误，在后一种关闭的情况下显示为运行时异常。
算法如下。 首先让我们假设某个任意节点是根。然后我们检查每个分支深度并找到更长的分支。之后我们完成重父化：我们将根更改为分支更高的节点，树的其余部分将成为新树的分支。 以这种方式，我们继续重新设置父级，直到我们到达相同长度的分支或深度相差一个节点的分支。此时我们将树视为高度平衡。 然后我们将（其中一个）较长的分支视为一棵单独的树，将原始树的其余部分视为另一棵单独的树，并通过最终重新设置父级再次平衡这两棵树。那些平衡树的根就是答案。
我们举个例子。假设我们有下面这棵树。
52
|
53
|
24-23-22-01-02-03-04-33-32-31-42-43-44
假设根是23个节点。所以我们最终要重生。
24
| 23
23 |__
| | |
22 22 24
| |
01 01
| |
02 02
| |
03 03
| |
04 04 04
|__ >> |__ >> … >> |_____
| | | | | | |
33 53 33 53 33 03 53
| | | | | | |
32 52 32 52 32 02 52
| | | |
31 31 31 01
| | | |
42 42 42 22
| | | |
43 43 43 23
| | | |
44 44 44 24
然后我们将最长的分支之一（33-32-31-42-43-44）视为一棵树，将树的其余部分视为另一棵树。
04
|__
| |
03 53 33
| | |
02 52 … 32
| |
01 31
| |
22 42
| |
23 43
| |
24 44
然后，我们依次平衡这两棵树。平衡后它们将如下。
02
|__
| | 31
01 03 |__
| | | |
22 04 42 32
| | | |
23 53 43 33
| | |
24 52 44
所以答案将是节点 02 和 31。
为了使实现足够有效，我们需要为每个节点兑现树深度。这样我们就不需要在每次重新设置父级后重新计算所有深度——每次重新设置父级后只需重新计算新根和一个新分支的深度就足够了。 所以，这里是实现。
class Node:
def __init__(self, val):
self.val = val
self.children = []
def construct_tree(pairs):
pairs = [tuple(list(sorted(pair))) for pair in pairs]
pairs.sort(reverse=True)
p, c = pairs.pop()
root = Node(p)
child = Node(c)
root.children.append(child)
nodes_dic = {p: root, c: child}
while pairs:
pair = pairs.pop()
p, c = pair
if c in nodes_dic:
p, c = c, p
if p in nodes_dic:
parent = nodes_dic[p]
node = Node(c)
parent.children.append(node)
nodes_dic[c] = node
else:
pairs.insert(0, pair)
return root
def get_depth(node, depths):
if node.val not in depths:
if not node.children:
depths[node.val] = 0
else:
depths[node.val] = 1 + max([get_depth(child, depths) for child in node.children])
return depths[node.val]
def reparent_tree(root, new_root, depths):
children = [child for child in root.children if child != new_root]
val = root.val
if val in depths:
del depths[val]
if new_root.val in depths:
del depths[new_root.val]
root = new_root
child = Node(val)
child.children = children
root.children.append(child)
return root
def balance_tree(root):
depths = {}
if len(root.children) == 0:
return root, None
if len(root.children) == 1:
root = reparent_tree(root, root.children[0], depths)
if get_depth(root, depths) < 2:
return root, root.children[0]
while True:
ls = [get_depth(node, depths) for node in root.children]
l1, l2 = list(sorted(ls))[-2:]
ind = ls.index(l2)
candidate_root = root.children[ind]
if l2 - l1 <= 1:
break
root = reparent_tree(root, candidate_root, depths)
return root, candidate_root
def f(pairs):
if len(pairs) <= 2:
return pairs[0]
root = construct_tree(pairs)
root, tree1 = balance_tree(root)
root.children.remove(tree1)
tree2 = root
tree1, _ = balance_tree(tree1)
tree2, _ = balance_tree(tree2)
return tree1.val, tree2.val
解决方案通过了我的测试用例——手工制作的和一些随机生成的，没有运行时错误，很难找出问题所在。