解法

完全二叉树可以看作是两个子树，一个是完全二叉树，另一个是满二叉树，满二叉树通过公式可以求得，而小的完全二叉树可以进一步的递归，继续分成下一个完全二叉树和满二叉树。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
   public int countNodes(TreeNode root) {

        if(root==null) return 0;
        int left=getLevel(root.left);
        int right=getLevel(root.right);

        if(left==right)
        {
            return countNodes(root.right)+(1<<left);
        }
        else
        {
            return countNodes(root.left)+(1<<right);
        }
    }

    public int getLevel(TreeNode node)
    {
        int level=0;
        while(node!=null)
        {
            node=node.left;
            level++;
        }
        return level;
    }
}