c - 确定恰好具有 4 个节点的子树数量的最佳方法是什么？

Question

考虑使用指针表示的有根 n 节点二叉树。确定恰好具有 4 个节点的子树数量所需时间的最佳上限是 O(n^a Log^b(n))。那么a+10b的值为__________。

---

我的尝试:

某处算法给出如下:

int print4Subtree(struct Node *root) {
    if (root == NULL)
      return 0;
    int l =  print4Subtree(root->left);
    int r =   print4Subtree(root->right);
    if ((l + r + 1) == 4)
       printf("%d ", root->data);
    return (l + r + 1); }

---

此算法运行 O(n) 次，因此答案为 1 。

它是正确的还是存在其他更好的算法？

请用正式/替代的方式解释一下。

Answer 1

在计算机科学中，子树 通常意味着它下面没有其他节点连接，但在图论中，术语子树 并不意味着这一点——它只是意味着一个子图(节点和边的子集)也是一棵树。所以例如如果你有一个 10 节点的路径，根在一端，根据图论定义有 7 个子树，而不是 1 个。根据图论定义通常有(很多)更多子树......这可能是问题中对数因子的来源。

另一方面，只有 常量 的 4 节点有根二叉树——我数了总共 14 棵(8 棵高度为 3 的树，4 棵高度为 2 的树，其中root 有 2 个 child ，以及 2 棵高度为 2 的树，其中 root 有 1 个 child )。因此，即使使用新的、更广泛的定义，也可以检查树中的每个节点，以查看 14 个可能的 4 节点有根二叉树中的哪一个以该节点为根，并将此计数添加到总计中，全部在O(n) 时间。