[LeetCode] 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.

Analysis: We just need find where the node stops at the lowest level. To achieve that, we need to compare the depth of the node on the left or the right side of the contour.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int countNodes(int depth, TreeNode *root)
    {
        if(!root) return 0;
        int res = 0;
        int level = 1;
        TreeNode* p = root->left;
        for(;p;p = p->right) level ++;
        
        if(level == depth) 
        {
            res = pow(2, depth-1) + countNodes(depth-1, root->right);
        }
        else
        {
            res = pow(2, depth-2) + countNodes(depth-1,  root->left);
        }
        return res;
    }
    int countNodes(TreeNode* root) {
        if(!root) return 0;
        TreeNode *p = root;
        int depth = 0;
        while(p)
        {
            depth ++;
            p = p->left;
        }
        return countNodes(depth, root);
    }
};