题目描述

给出一个完全二叉树，求出该树的节点个数。

C++ 代码

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root == nullptr) return 0;
        int h = 0;
        TreeNode *iter = root -> left;
        while(iter != nullptr)
        {
            ++h;
            iter = iter -> left;
        }
        if(h == 0) return 1;
        // 高度至少为1, 至少两层
        long long left = 1;
        long long right = (1 << h) - 1;
        while(left < right)
        {
            long long mid = left + (right - left) / 2;
            if(check(mid, h, root))
                left = mid + 1;
            else
                right = mid - 1;
        }
        long long result = (1 << h) - 1;
        if(check(left, h, root))
            result += left + 1;
        else
            result += left;
        return (int)result;
    }

private:
    bool check(long long mid, int h, TreeNode* root)
    {
        TreeNode *iter = root;
        for(int i = h - 1; i >= 0; --i)
        {
            if((mid >> i & 1) == 1)
                iter = iter -> right;
            else
                iter = iter-> left;
        }
        if(iter == nullptr)
            return false;
        else
            return true;
    }
};