我们有一个包含 n 个节点的二叉树。这棵树不一定是平衡的。对于此树的任何节点，如 x，我们计算此节点的 left 和 right 子树的大小(即节点数)，以及将此节点的标签设置为这两个值(右子树和左子树的值)的最小值。如果任何子树有零个节点，则此大小等于 0。以下哪项是正确的:
I) 标签的总和属于 O(n log n) 的顺序。
II) 有一棵树，它的标签之和属于 O(n) 阶。 (即:是否有可能得到一棵树，其标签的总和为 O(n)？)
III) 有一棵树，其标签的总和属于 O(n^2) 的顺序。
我的助教说其中两个是真的。我的问题是这些句子，谁能帮我描述一下？
最佳答案
我猜是 1 和 2。
1.) 考虑树的高度。高度和节点数 n 有 n = (2^h)-1 的关系。从这个关系中，我们可以得出 h = logn。现在，让我们来看看二叉树每一层的节点数。一个级别可以拥有的最大节点数是 (n/2)，这是最后一个级别(在完整的二叉树中，最后一个级别将有 n/2 个节点)。因此，计算最小值的最坏情况是(级别数)*(每个级别的节点数)=> n/2logn => O(nlogn)。
2.) 通过改变树的高度可以获得 0(n) 解。例如，如果考虑所有节点的子集，使得树的高度为零/一，则可以获得 O(n) 解决方案 - 对于总级别为二，最多可以有三个节点(根，左，右)，因此，这里不涉及最小计算。在这种情况下，我们没有额外的登录运行时间，我们以 O(n) 结束。
关于algorithm - 特殊的二叉树，一个棘手的问题？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37236802/