Leetcode 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 2hnodes inclusive at the last level h.

Solution 1: Use binary search. Each time check the left sub tree and right sub tree. One of them will be full filled and simple cal the result. The other one is not full filled and will be sub problem of root case. Complexity will be O(logn*logn)

 public class Solution {  
   public int countNodes(TreeNode root) {  
     if (root==null) return 0;  
     int left=0, right=0;  
     TreeNode l=root, r=root;  
     while (l!=null) {  
       l=l.left;  
       left++;  
     }  
     while (r!=null) {  
       r=r.right;  
       right++;  
     }  
     if (left==right) return (1<<left)-1;  
     return countNodes(root.left)+countNodes(root.right)+1;  
   }  
 }