原题链接在这里：https://leetcode.com/problems/count-complete-tree-nodes/
题目：
Given a complete binary tree, count the number of nodes.
Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
题解：
Complete Tree的定义是左右深度差不大于1.
递归调用函数，终止条件两个，一个是root == null, return 0. 另一个是左右高度相同说明是满树, return 2^height-1.
若是左右高度不同，递归调用求 左子树包含Node数 + 右子树包含Node数 + 1(自身).
Note:1. 用Math.pow(), 注意arguments 和 return type 都是double, 此处会TLE.
2. 用<<来完成幂运算，但注意<<的precedence比+，-还要低，需要加括号.
Time Complexity: O(h^2). worst case对于每一层都要求一遍当前点到leaf得深度.
假设只有最底层多了一个TreeNode 那么计算height就需要每层计算一遍h + (h-1) + (h-2) + ... + 1 = O(h^2).
Space: O(h), stack space.
AC Java:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int countNodes(TreeNode root) {
if(root == null){
return 0;
}
TreeNode p = root;
TreeNode q = root;
int leftDepth = 0;
int rightDepth = 0;
while(p!=null){
leftDepth++;
p = p.left;
}
while(q!=null){
rightDepth++;
q = q.right;
} if(leftDepth == rightDepth){
return (1<<leftDepth) - 1;
}else{
return countNodes(root.left) + 1 + countNodes(root.right);
}
}
}