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

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; 
} 

我明白这一点，但我不能完全肯定我理解的条件，如果（leftHeight == rightHeight）。这个怎么用？另外，有人可以解释一下按位操作以及为什么这样工作的原因？我不熟悉按位运算符。也许，如果有人可以用非按位代码替换这个条件，并且翻译那些将会完美的事情！

Answer 1

条件(leftHight == rightHight)在树的子树中，我们知道这是一棵完整的树意味着当前子树是一棵perfect（完整）二叉树。在一棵完美的二叉树中，除了没有孩子的叶节点外，每个节点只有两个孩子。

按位说明(2<<(left-1))-1与Math.pow(2, left) - 1相同。如果你看一下上面的链接，你会看到一个节点的高度h的完美二叉树数为(2**(k+1))-1

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 

现在： 在2一般权力可以被计算如下。对于（k + 1）减1的幂为2.

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