计算二叉树中的节点数 O(logn)^2
Counting the number of Nodes in Binary Tree O(logn)^2
我有一个问题，我需要找到时间复杂度为
的完整树中的节点数
O((log(n))^2) 例如(n 的对数)^2，我的成绩是
找到 h 即 h= log n （树的高度，因为它是一棵完整的树，总是向左移动）然后来到 h-1 处的每个节点并检查它是否有右节点，如果它有，那么它必须有一个左节点（因为完整的树）如果它没有然后检查它是否有一个左节点，就像那样计算节点的数量。
问题是我认为它是O(n)因为h = log(n)并且这个高度的节点数是2^(h-1)所以整个过程是O(n)并且不是 O( (log n)^2) ..
的输出
是 12 因为它有 12 个节点，时间复杂度为 O( (log n)^2)
非常感谢您的帮助！谢谢。
正如 Michael 所说，您必须以某种方式在您的问题中应用二进制搜索。
所以最简单的方法是通过这个算法：
- 首先，正如你所说，我们必须找到一棵树的高度，为此我们直接走到最左边的节点；
我们知道树的高度H，现在我们可以应用二分查找：
我将描述根的算法，对于每个下一个节点都是相同的：
每次我们搜索右子树最左边的叶子。
所以如果在高度H上有一个叶子，如图所示，然后用右边的child重复程序（找到树的右子树的最左边的叶子"root"是节点C）。
如果没有叶子，则对根的左边child重复同样的步骤。
首先，通过遍历left个指针，计算到最左边叶子的距离。然后用 right 指针做同样的事情。如果两个数字都是 n，那么您将拥有一棵具有 2^n - 1 个节点的完美树。
否则，它们不相等。然后第一个计数是某个数字 n+1，第二个是 n。我们需要探测 - 正如其他人所说的那样使用二进制搜索 - 完整的 n 深层节点（将根计算为第 1 层）以找到具有 0 或 1 children 的最左边。有 2^(n-1) 个节点要探测。在示例中，n=3，因此我们正在探测 4 个节点。
我们可以通过考虑数字 0..2^(n-1) - 1 中的位来探测该层。在示例中，这是 0..3（即 n-2 位）。在从根到叶的遍历中，0 位表示 "go left." 1 表示 "go right." 由于下面讨论的原因，您希望使用从最高位到 lowest-order 的位（在示例中，位 1,0) 从根到叶。不难看出，使用 0..2^(n-1) - 1 作为路径遍历 "instructions," 你将从左到右到达该层中的每个顶点。例如，2 的位为 10。这意味着从根开始，向右然后向左，这将带您到 F。
但是您当然不想搜索 n-deep 层中的每个顶点，因为那样会使您的搜索复杂化为 O(n)。相反，使用二进制搜索。首先在 [0..2^(n-1) - 1] 的中点尝试 "instruction"。如果找到 2 children，则将搜索括号缩小到大于中点的值。如果找到 0 children，则值较少。以这种方式继续，直到找到具有 1 child 的节点或括号大小为 1 并且有 0 children。后者意味着你找到了层中最左边的节点，没有 children.
现在我们可以轻松找到 children 的总数。向下到第 n 层的树部分有 2^(n-1) - 1 个节点，将您带到最终搜索节点的 "instruction" 告诉您第 n+1 层中有多少个节点。这些共同告诉你最终的答案。我会让你算出最后的细节。
我有一个问题，我需要找到时间复杂度为
的完整树中的节点数
O((log(n))^2) 例如(n 的对数)^2，我的成绩是
找到 h 即 h= log n （树的高度，因为它是一棵完整的树，总是向左移动）然后来到 h-1 处的每个节点并检查它是否有右节点，如果它有，那么它必须有一个左节点（因为完整的树）如果它没有然后检查它是否有一个左节点，就像那样计算节点的数量。
问题是我认为它是O(n)因为h = log(n)并且这个高度的节点数是2^(h-1)所以整个过程是O(n)并且不是 O( (log n)^2) ..
的输出
是 12 因为它有 12 个节点，时间复杂度为 O( (log n)^2)
非常感谢您的帮助！谢谢。
正如 Michael 所说，您必须以某种方式在您的问题中应用二进制搜索。 所以最简单的方法是通过这个算法：
- 首先，正如你所说，我们必须找到一棵树的高度，为此我们直接走到最左边的节点；
我们知道树的高度H，现在我们可以应用二分查找：
我将描述根的算法，对于每个下一个节点都是相同的：
每次我们搜索右子树最左边的叶子。
所以如果在高度H上有一个叶子，如图所示，然后用右边的child重复程序（找到树的右子树的最左边的叶子"root"是节点C）。
如果没有叶子，则对根的左边child重复同样的步骤。
首先，通过遍历left个指针，计算到最左边叶子的距离。然后用 right 指针做同样的事情。如果两个数字都是 n，那么您将拥有一棵具有 2^n - 1 个节点的完美树。
否则，它们不相等。然后第一个计数是某个数字 n+1，第二个是 n。我们需要探测 - 正如其他人所说的那样使用二进制搜索 - 完整的 n 深层节点（将根计算为第 1 层）以找到具有 0 或 1 children 的最左边。有 2^(n-1) 个节点要探测。在示例中，n=3，因此我们正在探测 4 个节点。
我们可以通过考虑数字 0..2^(n-1) - 1 中的位来探测该层。在示例中，这是 0..3（即 n-2 位）。在从根到叶的遍历中，0 位表示 "go left." 1 表示 "go right." 由于下面讨论的原因，您希望使用从最高位到 lowest-order 的位（在示例中，位 1,0) 从根到叶。不难看出，使用 0..2^(n-1) - 1 作为路径遍历 "instructions," 你将从左到右到达该层中的每个顶点。例如，2 的位为 10。这意味着从根开始，向右然后向左，这将带您到 F。
但是您当然不想搜索 n-deep 层中的每个顶点，因为那样会使您的搜索复杂化为 O(n)。相反，使用二进制搜索。首先在 [0..2^(n-1) - 1] 的中点尝试 "instruction"。如果找到 2 children，则将搜索括号缩小到大于中点的值。如果找到 0 children，则值较少。以这种方式继续，直到找到具有 1 child 的节点或括号大小为 1 并且有 0 children。后者意味着你找到了层中最左边的节点，没有 children.
现在我们可以轻松找到 children 的总数。向下到第 n 层的树部分有 2^(n-1) - 1 个节点，将您带到最终搜索节点的 "instruction" 告诉您第 n+1 层中有多少个节点。这些共同告诉你最终的答案。我会让你算出最后的细节。