我目前正在学习在线数据结构课程,并且这是其中一个作业任务; 请指导我如何得到答案,而不是给我答案。
以下是任务描述:
任务:给定一棵根树的描述。您的任务是计算并输出其高度。回想一下,(根)树的高度是节点的最大深度,或从叶子到根的最大距离。给定任意树,不一定是二叉树。
输入格式:第一行包含节点数n。第二行包含整数号码从-1到n-1的父节点。如果它们中的第i个(0 ≤ i ≤ n-1)为-1,则节点i为根,否则它是第i个节点的基于0的索引的父节点。可以保证只有一个根。可以保证输入表示一棵树。
约束条件:1 ≤ n ≤ 10^5.
我的当前解决方案有效,但当n>10^2时非常缓慢。以下是我的代码:
以下是任务描述:
任务:给定一棵根树的描述。您的任务是计算并输出其高度。回想一下,(根)树的高度是节点的最大深度,或从叶子到根的最大距离。给定任意树,不一定是二叉树。
输入格式:第一行包含节点数n。第二行包含整数号码从-1到n-1的父节点。如果它们中的第i个(0 ≤ i ≤ n-1)为-1,则节点i为根,否则它是第i个节点的基于0的索引的父节点。可以保证只有一个根。可以保证输入表示一棵树。
约束条件:1 ≤ n ≤ 10^5.
我的当前解决方案有效,但当n>10^2时非常缓慢。以下是我的代码:
# python3
import sys
import threading
# In Python, the default limit on recursion depth is rather low,
# so raise it here for this problem. Note that to take advantage
# of bigger stack, we have to launch the computation in a new thread.
sys.setrecursionlimit(10**7) # max depth of recursion
threading.stack_size(2**27) # new thread will get stack of such size
threading.Thread(target=main).start()
# returns all indices of item in seq
def listOfDupes(seq, item):
start = -1
locs = []
while True:
try:
loc = seq.index(item, start+1)
except:
break
else:
locs.append(loc)
start = loc
return locs
def compute_height(node, parents):
if node not in parents:
return 1
else:
return 1 + max(compute_height(i, parents) for i in listOfDupes(parents, node))
def main():
n = int(input())
parents = list(map(int, input().split()))
print(compute_height(parents.index(-1), parents))
示例输入:
>>> 5
>>> 4 -1 4 1 1
这将产生一个解决方案为3
,因为根是1
,3
和4
从1
分支出,然后0
和2
从4
分支出,这使得该树的高度为3
。
如何改进此代码以使其在3秒的时间基准下运行?此外,在另一种语言中是否更容易实现?