222. 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 2^h nodes inclusive at the last level h.

Solution:

Brutal force: BFS, DFS, You can't pass OJ because of time limitation. Because we are not use any characteristics of complete binary tree.

For a given complete binary tree root, assume the height of the tree is h, either its left child is a perfect tree with height of h-1 or its right child is a perfect tree with height of h-2;

Eg. if the last node is in the left child, then the right tree is a perfect tree while if the last node is in the right child, the left tree is a perfect tree. 

For a perfect tree we can get the nodes count easily by doing Math.pow(2, h), or left shift h places. 

We can recursively calculate the counts by this technique. 

  public int countNodes(TreeNode root) {  
     if(root==null) return 0;  
    int lh=getHeight(root.left);  
     int rh=getHeight(root.right);  
     if(lh==rh) return (1<<lh)+countNodes(root.right);  
     else return (1<<rh)+countNodes(root.left);  
   }  
   public int getHeight(TreeNode root){  
     int height=0;  
     while(root!=null){  
       root=root.left;  
       height++;  
     }  
     return height;  
   }