題目來源
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.
給一個(gè)完整二叉樹，求節(jié)點(diǎn)數(shù)目。
最直觀的方法就是遍歷，例如用深度優(yōu)先遍歷，代碼如下：

/**
 * 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(TreeNode* root) {
        int l = 0;
        TreeNode *cur = root;
        int res = 0;
        if (root)
            dfs(root, res);
        return res;
    }
    
    void dfs(TreeNode* node, int &count)
    {
        if (node)
            count++;
        else 
            return;
        dfs(node->left, count);
        dfs(node->right, count);
    }
};

沒錯(cuò)，又TLE了。想想除了最后一層，其他的都可以直接算出來，因?yàn)槭菨M的，但是最后一層的節(jié)點(diǎn)數(shù)目應(yīng)該怎么算呢？
沒有什么特別直觀的想法。
看了下答案，主要是這么一個(gè)類似的剪枝過程，就是假如是滿二叉樹就直接算，不是的話就看左右子樹的情況，遞歸。

/**
 * 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(TreeNode* root) {
        TreeNode *l = root, *r = root;
        int hl = 0, hr = 0;
        while (l) {
            hl++;
            l = l->left;
        }
        while (r) {
            hr++;
            r = r->right;
        }
        return (hl == hr) ? (pow(2, hl) - 1) : (1 + countNodes(root->left) + countNodes(root->right));
    }
};