Leetcode 222: count complete tree nodes

 count the number of nodes in a complete binary tree.

这个题目咋一看是求树的节点数，用暴力解发现超时，time complexity; O(N).
complete binary tree: 只有最后一层是不complete的，其它层都是full tree， 如果对于每个tree node, root node，这课subtree是full的，即左子树高度和右子树高度相同，那么就可以直接用 2 ^h -1求得子树节点数， 对于左右子树高度不同的，再用left + right + 1的暴力法来做，这样做的话，对于一棵complete binary tree，只有一次left != right的情况，时间复杂度是计算左右子树高度的复杂度： O（h ^ 2）

有一个小技巧： 2^h 可以直接用移位操作， 2 << (h-1)



class Solution {
private:
    int getLeft(TreeNode* root) {
       int left = 0;
       while (root) {
           root = root->left;
           left++;
       }
       return left;
    }
    int getRight(TreeNode* root) {
        int right = 0;
        while (root) {
            root = root->right;
            right++;
        }
        return right;
    }
public:
    int countNodes(TreeNode* root) {
        //base case
        if (root == NULL) return 0;
        int left = getLeft(root);
        int right = getRight(root);
        if (left == right) {
            return (2 << (left-1)) -1;
        } else {
            return countNodes(root->left) + countNodes(root->right)+1;
        }
       
    }
};