0

我正在尝试解决一个练习，其中给你一个完美的三叉树，其中每个节点都包含一个整数。我们要计算有多少内部节点符合这些规范：

  1. 节点的数量大于其所有子节点
  2. 它最大的孩子是中间那个

例如，在下面的树中，只有 3 个节点符合这些规范 例子

设计和分析一种分治算法，计算满足规范的节点数。这个算法应该是O(n)，其中n是叶子的个数，n是3的幂。不考虑树的数据结构，只解释一个算法

所以我尝试设计这个算法： 算法 我是算法设计的新手，我不知道我所做的时间复杂度是多少，或者即使它是一个分而治之的算法。如果您知道如何帮助我计算时间复杂度或检查它是否真的是一个分而治之的解决方案，请告诉我。另外，如果您有比我更好的想法，请提供帮助。谢谢

4

1 回答 1

2

首先，几乎每个递归都可以被视为分而治之，因为您将问题拆分为子问题。

其次，请注意您最多访问树的每个节点一次，因此运行时间确实是您希望的 O(n)

  • 我刚刚注意到您定义n为叶子的数量，而不是节点的数量，但分析仍然有效，因为对于高度的树h，节点数量是1+3+..+3^h-1 = O(3^h)并且在h级别中正好有3^h叶子。所以算法确实在 ~O(3n)=O(n) 时间内运行

最后一点，我觉得你做的其实很好！但在实践中，我认为在这种情况下编写递归主要是通过“分支”而不是通过级别，这意味着你先深入再深入。为了更清楚地说明这一点，我的意思是，最终代码将如下所示：

def countSpeacialNodes (Node t):
if t doesnt have children: return 0
if t is bigger than its children AND t's biggest child is the middle:
return 1+CSN(t.left)+CSN(t.middle)+CSN(t.right)
else return CSN(t.left)+CSN(t.middle)+CSN(t.right)

所以总结一下，你可以注意到在这里推进到树的深处，然后到树的“宽”，而且没有必要标记节点

希望它有一点帮助

于 2021-02-09T07:35:38.123 回答