完全二叉树的节点个数

题目描述：

求一个完全二叉树的节点个数。 leetcode链接

解题

1.通用解法

对于普通的二叉树，我们可以利用深度优先和广度优先方式，在遍历节点的过程中统计节点的个数，在此题中也可以采用这种方式，下面给出代码，不过多赘述。

代码如下：

   /**
   * 深度优先
   */
public int countNodes(TreeNode root) {
       if(root== null) return 0;
       return countNodes(root.left)+countNodes(root.right)+1;
   }

/**
* 广度优先
*/
public int countNodes(TreeNode root) {
       if (root == null) return 0;
       Queue<TreeNode> queue = new LinkedList<>();
       queue.add(root);
       int res = 0;
       while (!queue.isEmpty()) {
           int size = queue.size();
           for(int i=0;i<size;i++){
               TreeNode node = queue.poll();
               res++;
               if (node.left != null) queue.offer(cur.left);
               if (node.right != null) queue.offer(cur.right);
           }
       }
       return res;
   }

2.完全二叉树解法

但是这并没有达到本题考察的目的，题目中指出该二叉树为完全二叉树[^1]，所以应该利用其特点来解题。我们知道满二叉树的计算公式是：2的深度次方-1，而一棵完全二叉树虽然无法直接利用该公式计算，但在它的左子树或右子树中一定可以找到满二叉树，而那部分完全可以借助满二叉树的计算公式。具体思路以注释形式体现在代码中。

方框中为在子树中找到的满二叉树:

/**
    * 利用到完全二叉树的特点
    * 完全二叉树可以看成多个满二叉树拼接而成，满二叉树结点个数用2^n-1来计算，n表示层数
    */
   public int countNodes(TreeNode root) {
       if(root== null) return 0;
       //在完全二叉树中，如果一直向左的深度与一直向右的深度相等，则说明是满二叉树，普通二叉数没有这个特点
       //分别计算深度。为什么初始值设为1呢？如果两值计算出来相等，需要利用公式2的n次方来计算，如果值是1（left=right=null即二叉树只有一个根结点），则返回结果为2^1-1=1;如果值是2，则返回结果是2^2-1=3
       int leftDepth=1;
       int rightDepth=1;
       TreeNode left=root.left;
       TreeNode right=root.right;
       while(left!=null){
           left=left.left;
           leftDepth++;
       }
       while(right!=null){
           right=right.right;
           rightDepth++;
       }
       //相等表示该树是满二叉树，运用公式计算节点数。因为后面用到了递归，所以此处的树就不一定是原树了，也可能是子树，即某棵子树为满二叉树。
       if(leftDepth==rightDepth){
           return (int)(Math.pow(2,leftDepth) -1);
       }
       //不是满二叉树则向左右子树寻找满二叉树并将求得的结点数以及根结点那一个加起来，这样一层一层递归最终求得整棵树的节点数
       return countNodes(root.left)+countNodes(root.right)+1;
   }