222. Count Complete Tree Nodes

My intuition is level order traversal. The key is to find the leaf number in last level. However, it can be done by DFS. The idea is to find the complete tree in subtrees. The complete tree has an important property that the depth of left-most leaf is equal to the depth of right-most leaf. If the tree is complete simple return the total number. If not, search the complete tree in left and right child.

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    int countNodes(TreeNode* root) {  
13:      if (root == NULL) return 0;  
14:      int lc = 0, rc = 0;  
15:      TreeNode *left = root, *right = root;  
16:      while (left) { lc++; left = left->left; }  
17:      while (right) { rc++; right = right->right; }  
18:      if (lc == rc) return (1 << lc)-1;  
19:      return 1 + countNodes(root->left) + countNodes(root->right);  
20:    }  
21:  };