假设r是树的根(可以是非二进制的),c是r的子节点,并且每个节点都包含一个整数。
Algorithm findMax(r)
if r = null return null
int maxValue = r.value
if r.isLeaf return maxValue;
for each child c of r do{
if findMax(c) > maxValue
maxValue = findMax(c)
}
return maxValue
发布于 2018-10-23 01:12:54
目前,当考虑n
为树中的节点数时,其复杂度为O(n)。
对于根的每个子节点,您可以对c
中的所有子树根调用递归函数。所以基本上,你在这个图上执行DFS,在你的例子中,它使得O(V+E) ->,当这个图是一棵树时,它等于O(V)。
注意,您在if语句中调用了findMax
的递归函数-如果为真,则重新计算它-这会将复杂度增加到O(2*n)。计算一次findMax
函数,将其结果赋给本地变量,并用它检查和更新maxValue
,将复杂度降低到O(n)。
https://stackoverflow.com/questions/52933573
复制相似问题