你的树需要重新修整
在图论中，树就是没有圈的任何图。但是在计算机科学中，我们经常使用有根的树。有根的树就像树，除非它们有一个特定的节点作为“根”，所有的计算都是从根开始的。
根树的深度是最小的n数，因此在n步骤中可以从根到达树的任何节点。如果根节点选择不当且深度较高，这可能意味着从根到特定节点需要采取许多步骤。
随着时间的推移，我们执行计算，我们的根树可能会改变形状，所以，我们想要“重新根”的树。也就是说，在不改变底层树的情况下，改变树的根，从而使产生的根树具有尽可能低的深度。
任务
在这个挑战中，你将被赋予一个在每个顶点都有正整数的根树作为输入。你应该输出重新扎根的树。这是一棵树，它的根被选择来最小化深度，但在其他方面是相同的。
您可以采取任何合理的格式输入，但请说明您的格式，以便您的答案可以测试。您应该使用相同的格式输入和输出。输入总是至少有一个节点。
这是密码-高尔夫，所以答案将以字节为单位，目标是最小化源代码的大小。
测试用例
在测试用例中，我们将树表示为节点列表。每个节点都是包含其值的元组，以及表示为其列表中的索引的子节点列表。根节点位于索引0处。
这种表示树的方式并不是唯一的，所以如果使用这种格式，可能会得到与给定结果同构但不完全相同的输出。
[(1,[1]),(9,[2]),(5,[])] -> [(9,[1,2]),(1,[]),(5,[])]
[(1,[1]),(9,[2]),(5,[3]),(7,[])] -> [(9,[1,2]),(1,[]),(5,[3]),(7,[])] or [(5,[1,3]),(9,[2]),(1,[]),(7,[])]
[(1,[1]),(8,[2,3]),(7,[]),(9,[])] -> [(8,[1,2,3]),(1,[]),(7,[]),(9,[])]回答 3
Code Golf用户
发布于 2022-01-07 11:29:03
Wolfram语言(数学)，63字节
GraphTree[g=UndirectedGraph@TreeGraph@#,Last@GraphCenter@g,#&]&将输入作为树对象，例如，Tree[1, {Tree[9, {Tree[5, None]}]}]。
在Mathematica 12.3中引入了树状物体，所以没有TIO。
测试用例的输出：
Tree[1, {Tree[9, {Tree[5, None]}]}] -> Tree[9, {Tree[1, None], Tree[5, None]}]
Tree[1, {Tree[9, {Tree[5, {Tree[7, None]}]}]}] -> Tree[9, {Tree[1, None], Tree[5, {Tree[7, None]}]}
Tree[1, {Tree[8, {Tree[7, None], Tree[9, None]}]}] -> Tree[8, {Tree[1, None], Tree[7, None], Tree[9, None]}]Wolfram语言(数学)，63字节
-3字节，这要感谢@att。
-(-#//.-a_[b___,c_@d___,e___]/;Depth@b?e<Depth@!d:>-b~a~e~c~d)&将输入作为数学表达式，例如1[9[5[]]]。
测试用例的输出：
1[9[5[]]] -> 9[1[], 5[]]
1[9[5[7[]]]] -> 9[1[], 5[7[]]]
1[8[7[], 9[]]] -> 8[1[], 7[], 9[]]或者59个字节(如果我们可以将输入作为-1[9[5[]]] )(我不确定在减号前加上是否是一种合理的格式。输出也有这个减号)：
#//.-a_[b___,c_@d___,e___]/;Depth@b?e<Depth@!d:>-b~a~e~c~d&Code Golf用户
发布于 2022-01-07 17:35:25
Python3,527字节：
from itertools import*
p=lambda x,i=0:[(x[i][0],x[j][0])for j in x[i][1]]+p(x,i+1)if i<len(x)else[]
d=lambda x,i=0:1+(max(d(x,l)for l in x[i][1])if x[i][1]else 0)
def f(n,p,c,u=[]):
if not p:yield c
else:
if(x:=(i:=n.index)(p[0][0]))<(y:=i(p[0][1]))and y not in u:yield from f(n,p[1:],c[:x]+[(c[x][0],c[x][1]+[y])]+c[x+1:],u+[y])
elif x not in u:yield from f(n,p[1:],c[:y]+[(c[y][0],c[y][1]+[x])]+c[y+1:],u+[x])
e=lambda x:min([j for k in permutations([i[0]for i in x],len(x))for j in f(k,p(x),[(i,[])for i in k])],key=d)Code Golf用户
发布于 2022-01-08 05:41:36
JavaScript + DOM，154个字节
n=>R(D([R(D([n]))]).slice(P.length/2))
D=(h,...t)=>P=h&&D(...t,...[...h[0].children].map(x=>[x,...h]))||h
R=([c,...p])=>p[c.remove(),0]&&c.append(R(p))||c输入根HTMLElement。在重新根之后输出新根。
f=
n=>R(D([R(D([n]))]).slice(P.length/2))
D=(h,...t)=>P=h&&D(...t,...[...h[0].children].map(x=>[x,...h]))||h
R=([c,...p])=>p[c.remove(),0]&&c.append(R(p))||c
tree2Dom = ([name, children], parent = document.createElement('div')) => {
parent.id = name;
children.forEach(node => parent.append(tree2Dom(node)));
return parent;
};
dom2Tree = node => [node.id, [...node.children].map(child => dom2Tree(child))];
testcases = [
['1', [['9', [['5', []]]]]],
['1', [['9', [['5', [['7', []]]]]]]],
['1', [['8', [['7', []], ['9', []]]]]],
];
testcases.forEach(t => {
console.log(JSON.stringify(dom2Tree(f(tree2Dom(t)))));
});有评论
// Find out the deepest element in root, output that element and all its parents
D=(h,...t)=>P=h&&D(...t,...[...h[0].children].map(x=>[x,...h]))||h
// Re-root the tree to c, input c and its parents
R=([c,...p])=>p[c.remove(),0]&&c.append(R(p))||c
// Find out the new root and re-root
n=>R(D([R(D([n]))]).slice(P.length/2))https://codegolf.stackexchange.com/questions/240711
复制相似问题
腾讯云开发者
