20.11.24 leetcode222

题目链接：https://leetcode-cn.com/problems/count-complete-tree-nodes/

题意：利用完全二叉树的性质，求完全二叉树的结点数。

分析：如果是单纯的二叉树，直接用dfs或者bfs。针对本题，首先我们得知道完全二叉树的性质是：除了最下面一层，中间每层结点数是满的，且最下面一层的结点都位于最左边。在求得层数后，除了最下面一层的所有层的结点数可以很轻松的求到，我们的任务主要是求最下面一层有多少结点。这里可以采用二分法来快速求得最下面一层，而在判断某个结点是否存在的时候，可以利用位运算，具体来说，对于某个结点，我们用二进制来表示的话，从根结点1开始，从根节点往左，就是添0，往右就是添1，以5为例，其二进制是101,而它就是从根节点左结点的右结点，所有可以利用二进制来快速的判断是否存在某个结点。

/**
 * 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) {
        if(root==nullptr)return 0;
        int level=0;
        TreeNode* node=root;
        while(node->left!=nullptr){
            level++;
            node=node->left;
        }
        if(level==0)return 1;
        int ans=1;
        int low=1<<level,high=(1<<(level+1))-1;
        while(low<=high){
            int mid=(high+low)/2;
            if(exist(mid,level,root)){
                ans=mid;
                low=mid+1;
            }
            else{
                high=mid-1;
            }
        }
        return ans;
    }

    bool exist(int k,int level,TreeNode* root){
        int bit=1<<(level-1);
        TreeNode* node=root;
        while(node!=nullptr&&bit>0){
            if(!(bit&k)){
                node=node->left;
            }
            else node=node->right;
            bit>>=1;
        }
        return node!=nullptr;
    }
};