LeetCode 222. 完全二叉树节点个数（方法二）

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

解题思路：前面讲解了递归的方式求解此题。但是递归并没有利用二叉树的性质。在方法二中

充分利用完全二叉树的性质，并结合二分法来求解此题。完全二叉树除去最后一层，其余层都

是满的，而且最后一层中的所有节点都集中在左侧。设二叉树的深度为d(这里的d从0开始计数)，

则前d-1层的节点个数为2^d-1，最后只需计算出最后一层的节点的个数将其相加返回即可。

最后一层的节点都集中在树的左侧，所以可以通过二分法来进行计算。

其LeetCode C++参考代码如下：

/**
 * 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){
              return 0;
          } 
          int d=countDepth(root);
          if(d==0){
              return 1;
          }
          int left=0,right=pow(2,d)-1;
          while(left<=right){
              int idx=left+(right-left)/2;
              if(exist(idx,d,root)){
                  left=idx+1;
              }
              else{
                  right=idx-1;
              }
          }
          return pow(2,d)+ left-1;
    }



    int countDepth(TreeNode* root){
        int d=0;
        while(root->left){
            d+=1;
            root=root->left;
        }
        return d;
    }
    bool exist(int idx,int d,TreeNode* node){

       int left=0,right=pow(2,d)-1;
       for(int i=0;i<d;i++){
           int pivot=left+(right-left)/2;
           if(idx<=pivot){
               right=pivot;
               node=node->left;
           }
           else{
               left=pivot+1;
               node=node->right;
           }
       }
       return node!=NULL;



    }




};