6_7 完全二叉树计数

给定一棵完全二叉树的根节点root，返回这棵树的节点个数。如果完全二叉树的节点数为N，请实现时间复杂度低于O(N)的解法。

给定树的根结点root，请返回树的大小。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/

class CountNodes {
public:
    int get_depth(TreeNode* root)
    {
        int res = 0;
        while(NULL != root){
            ++res;
            root = root->left;
        }
        return res;
    }
    int count(TreeNode* root) {
        // write code here
        int n = get_depth(root);
        if(1 == n){
            return 1;
        }
        int n_r = get_depth(root->right);
        if(n == n_r+1){
            return pow(2, n-1) + count(root->right);
        }else{
            return pow(2, n-2) + count(root->left);
        }
    }
};