计算完整二叉树中的节点数

Question

我想计算完整二进制树中的节点数,但我能想到的只是遍历整个树.这将是一个O(n)算法,其中n是树中节点的数量.什么是最有效的算法来实现这一目标？

Answer 1

假设我们从树的左右脊上走下来确定它们的高度.我们要么发现它们是相同的,在这种情况下最后一行是满的,否则我们会发现它们是不同的.如果高度返回相同(比如高度为h),那么我们知道有2个^h - 1个节点,我们就完成了.

否则,高度必须分别为h + 1和h.我们知道当时至少有2 ^h - 1个节点,加上树底层的节点数.那么,问题是如何解决这个问题.一种方法是在最后一层找到最右边的节点.如果您知道该节点所在的索引,您确切知道最后一层中有多少节点,因此您可以将其添加到2 ^h - 1并且您已完成.

如果您有一个左侧高度为h + 1的完整二叉树,则可能在最后一层中有1到2个^小时 - 1个可能的节点.那么问题是如何尽可能有效地确定这一点.

幸运的是,由于我们知道最后一层中的节点从左到右填充,我们可以使用二进制搜索来尝试找出最后一层中最后一个填充节点的位置.从本质上讲,我们猜测它可能是哪个索引,从树的根部走到那个叶子的位置,然后在那里找到一个节点(所以我们知道底层最右边的节点是那个节点或在右边)或我们没有(所以我们知道底层最右边的节点必须纯粹在当前位置的右边).我们可以通过使用数字k中的位来向下走到底层第k个节点的位置来引导搜索:我们从根开始,然后如果k的第一位为0则向左移动,如果是k的第一位是1,然后以相应的方式使用剩余的位来向下走树.我们这样做的总次数是O(h),每次探测花费时间O(h),所以这里完成的总工作量是O(h ²).由于h是树的高度,我们知道h = O(log n),因此该算法需要时间O(log ² n)时间才能完成.

我不确定是否可以改进这种算法.但是,我可以在任何正确的算法上获得Ω(log n)下限.我将争辩说,在所有情况下始终正确的任何算法都必须检查树的最后一行中最右边的叶节点.要知道原因,假设有一个树T,算法不会这样做.假设算法在底行中检查的最右边节点是x,底行中实际最右边的节点是y,并且算法检测到的底行中最左边的丢失节点是z.我们知道x必须在y的左边(因为算法没有检查底行中最左边的节点)并且y必须在z的左边(因为y存在而z不存在,所以z必须比y)更靠右边.如果你考虑算法的"知识"在这一点上是什么,算法不知道是否有任何节点纯粹在x的右边或纯粹在z的左边.因此,如果我们给它一个修改后的树T',我们删除了y,算法就不会注意到任何东西已经改变了,并且在T和T'上会有完全相同的执行路径.然而,由于T和T'具有不同数量的节点,因此算法必须在其中至少一个上是错误的.由于走下树所需的时间,检查此节点至少花费时间Ω(log n).

简而言之,你可以使用上面的O(log ² n)时间算法比O(n)做得更好,你可能做得更好,尽管我不完全确定如何或是否可能.我怀疑这不是因为我怀疑二进制搜索是检查底行和路径长度到探测节点的最佳方式,即使考虑到它们共享共同的节点,也是Θ (log ² n),但我不确定如何证明它.

希望这可以帮助!

Answer 2

public int leftHeight(TreeNode root){
    int h=0;
    while(root!=null){
        root=root.left;
        h++;
    }
    return h;
}
 public int rightHeight(TreeNode root){
    int h=0;
    while(root!=null){
        root=root.right;
        h++;
    }
    return h;
}
public int countNodes(TreeNode root) {
    if(root==null)
        return 0;
    int lh=leftHeight(root);
    int rh=rightHeight(root);
    if(lh==rh)
        return (1<<lh)-1;
    return countNodes(root.left)+countNodes(root.right)+1;

}

在每次递归调用中，我们需要沿着完全二叉树的左右边界遍历，计算左右高度。如果它们相等，则树充满了 2^h-1 个节点。否则我们在左子树和右子树上递归。第一次调用是从根 (level=0) 开始的，需要 O(h) 时间来获得左右高度。我们一直递归，直到我们得到一个完全二叉树的子树。在最坏的情况下，我们可能会去直到叶节点。所以复杂度将是 (h + (h-1) +(h-2) + ... + 0)= (h(h+1)/2)= O(h^2)。此外，空间复杂度是大小调用栈，O(h)。注意：对于完整的二叉树 h=log(n)。

Answer 3

如果二叉树绝对是完整的（与维基百科文章中定义的“几乎完整”或“几乎完整”相反），您应该简单地沿着树的一个分支向下下降到叶子。这将是 O(logn)。然后将两个深度的幂相加。所以 2^0 + 2^1... + 2^d