如何在不访问每个节点的情况下计算完整二叉树中的节点数？

Question

我有计算完整二叉树中节点数量的简单解决方案：

public int countNodes(TreeNode root) {
    if (root == null) { return 0; }
    return 1 + countNodes(root.left) + countNodes(root.right);
}

我明白了。但是，我知道它效率低下，因为它必须访问每个节点。我在网上找到了另一个解决方案：

public int countNodes(TreeNode root) {
    if(root==null)
        return 0;

    int left = getLeftHeight(root)+1;    
    int right = getRightHeight(root)+1;

    if(left==right){
        return (2<<(left-1))-1; //having a hard time here
    }else{
        return countNodes(root.left)+countNodes(root.right)+1;
    }
}

public int getLeftHeight(TreeNode n){
    if(n==null) return 0;

    int height=0;
    while(n.left!=null){
        height++;
        n = n.left;
    }
    return height;
}

public int getRightHeight(TreeNode n){
    if(n==null) return 0;

    int height=0;
    while(n.right!=null){
        height++;
        n = n.right;
    }
    return height;
}

我理解这一点，但我不完全确定我理解条件 if (leftHeight == rightHeight)。这是如何运作的？另外，有人可以解释一下按位运算及其有效的原因吗？我不熟悉按位运算符。也许，如果有人可以用 none-bitwise 代码替换该条件，并翻译发生的事情，那将是完美的！

Answer 1

条件(leftHight == rightHight) in a subtree of a tree that we know is a complete tree 表示当前子树是perfect（满）二叉树。在完美的二叉树中，每个节点都恰好有两个 children，除了没有 children 的叶节点。

按位语句(2<<(left-1))-1与Math.pow(2, left) - 1相同。一般2的次方可以计算如下：

2<<0 //equals 2 to the power of 1. 2 is shifted zero bits to the left
2<<1 //equals 2 to the power of 2, 2 is shifted 1 bit to the left
2<<2 // equals 2 to the power of 3, 2 is shifted 2 bits to the left
2<<k // equals 2 to the power of k+1, 2 is shifted k bits to the left

现在，如果您查看上面的 link，您会发现高度为 h 的完美二叉树中的节点数为 (2**(k+1))-1。即 2 的 (k+1) 减 1 次方。

在上面的代码中 left 是 height+1 注意代码中的加一。因此 (2<<(left-1))-1 实际上是在计算完美二叉树中的节点数。

如何在不访问每个节点的情况下计算完整二叉树中的节点数？

How to count number of nodes in a complete binary tree without visiting each node?

java

algorithm

binary-tree

bitwise-operators