确定恰好具有 4 个节点的子树数量的最佳方法是什么？
What is the best way to determine the number of subtrees having exactly 4 nodes?
考虑使用指针表示的有根 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。
它是否正确或存在其他更好的算法？
你能用formal/alternative的方式解释一下吗？
在计算机科学中，一个子树通常意味着它下面没有进一步的节点连接，但在图论中，术语子树 并不意味着这一点——它只是意味着一个子图（节点和边的子集）也是一棵树。所以例如如果你有一个 10 节点的路径，根在一端，根据图论定义有 7 个子树，而不是 1 个。根据图论定义通常有（很多）更多子树......这可能是问题中对数因子的来源。
另一方面，只有一个常量 4 节点有根二叉树——我一共数了 14 棵（8 棵高度为 3 的树，4 棵高度为2 棵根有 2 children 的树，和 2 棵高度为 2 的树，其中根有 1 child)。因此，即使使用新的、更广泛的定义，也可以检查树中的每个节点，以查看 14 个可能的 4 节点有根二叉树中的哪一个以该节点为根，并将此计数添加到总计中，全部在O(n) 次。
考虑使用指针表示的有根 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。
它是否正确或存在其他更好的算法？
你能用formal/alternative的方式解释一下吗？
在计算机科学中，一个子树通常意味着它下面没有进一步的节点连接，但在图论中，术语子树 并不意味着这一点——它只是意味着一个子图（节点和边的子集）也是一棵树。所以例如如果你有一个 10 节点的路径，根在一端，根据图论定义有 7 个子树，而不是 1 个。根据图论定义通常有（很多）更多子树......这可能是问题中对数因子的来源。
另一方面，只有一个常量 4 节点有根二叉树——我一共数了 14 棵（8 棵高度为 3 的树，4 棵高度为2 棵根有 2 children 的树，和 2 棵高度为 2 的树，其中根有 1 child)。因此，即使使用新的、更广泛的定义，也可以检查树中的每个节点，以查看 14 个可能的 4 节点有根二叉树中的哪一个以该节点为根，并将此计数添加到总计中，全部在O(n) 次。