222. 完全二叉树的节点个数

class Solution {
public:
    int countNodes(TreeNode* root) {
        //最为暴力的方式就是去遍历，然后一个个计数！
        //来个层序遍历
        queue q;
        if(root == nullptr)return 0;
        q.push(root);
        int count = 0;
        while(!q.empty())
        {
            int size = q.size();
            for(int i = 0; i < size; i++){
                root = q.front();
                q.pop();
                count++;
                if(root->left)q.push(root->left);
                if(root->right)q.push(root->right);
            }
        }
        return count;
    }
};

 最简单的方式就是遍历，所以这里直接是利用遍历去计数的。但是优化也是有门道的：

你像这里的二叉树是完全二叉树，这是个特殊的情况，你并没有利用这样一点。所以说代码不具备针对性，那写出来的肯定是低效的。

那么怎么升级呢，就需要利用题目的这一特点去写代码：

class Solution {
public:
    int countNodes(TreeNode* root) {
        //我还可以少遍历一点
        queue q;
        if(root == nullptr)return 0;
        q.push(root);
        int lastFloor = 0;
        int floorCount = 0;
        while(!q.empty()){
            floorCount++;
            int size = q.size();
            for(int i = 0; i < size; i++){
                root = q.front();
                q.pop();
                if(root->left){
                    q.push(root->left);
                }
                else{
                    lastFloor = 2 * i;
                    return lastFloor + pow(2, floorCount) - 1;
                }
                if(root->right){
                    q.push(root->right);
                }
                else{
                    lastFloor = 2 * i + 1;
                    return lastFloor + pow(2, floorCount) - 1;
                }
            }
        }
        return 0;
    }
};

上边的这个解法就利用了部分的性质：就是只遍历了前n-1层，然后直接通过计算给出第n层的数目。而且前n-1层大多数情况下也并没有遍历完，前n-1层的总数是利用等比数列进行计算得出的。

有一个点就是：(59条消息) C++n次幂和n次方根计算_seven_tree的博客-CSDN博客_c++ n次方

对于2的n次方写法：利用了接口pow，同时如果开n次根号的话，需要转成double，上边也说了！

            cout< 
class Solution {
    public int countNodes(TreeNode root) {
    	if(root == null) {
    		return 0;
    	}
    	int left = countNodes(root.left);
    	int right = countNodes(root.right);
    	
    	return left+right+1;
    	
    }
}
 
上边是暴力递归的解法，但是也只是一个娱乐解法！
 
但是这里面有点思想的东西还是值得学习的，其实目前见到的递归玩法可以主要分为两类，一种是通过递归把问题大事化小小事化了的，还有一种就是针对二叉树这种数据结构实现递归完成遍历的。而后者的存在就是得益于二叉树这种数据结构的特性和递归特别契合！
 
这里就是直接利用了二叉树进行递归完成了遍历。当然这里就是利用了前者的第一种，就是当前树的节点就等于左右子树的节点数目加1，也就是只需要求左右子树的节点数目，那么左右子树又可以用同样的思路去处理，那么就是实现功能A的时候又用到了功能A：找出一个树的所有节点。
 
public:
    int countNodes(TreeNode* root) {
        if (root == NULL) return 0;
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
};
 
这是更为精简的版本！
 
但是上面的这些递归做法都并没有利用完全二叉树的特性去解题。
 
要想得到更少时间复杂度的解法还得特别针对一下，通解是永远无法超越特解的！
 
这里就要涉及到完全二叉树的特点了，完全二叉树他的最大的两个子树一定有一颗是满二叉树。那么思路就来了，满二叉树是可以直接计算的，那么是否可以把整个树都转换成二叉树这么算呢？
 
首先一个完全二叉树，有一个儿子是完美的，一个是完全的。那么总的节点数目就等于完全的加完美的。
 
那么完全的儿子咋算呢？那不又是一个完美加一个完全再加1么！
 
那这个时候就是想要实现功能A，在实现的过程中又用到了功能A，那么不就是递归吗？同时这个思路也完全利用了完全二叉树的特点！
 
那么问题来了，怎么判断一个树是不是完美二叉树呢？那就是最左边和最右边的两条链是不是一样长的。
 
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root == nullptr)return 0;
        TreeNode* node = root;
        int leftLenth = 1;
        int rightLenth = 1;
        for(; node->left != nullptr; node = node->left, leftLenth++);
        node = root;
        for(; node->right != nullptr; node = node->right, rightLenth++);
        if(leftLenth == rightLenth){
            return pow(2, leftLenth) - 1;
        }
        
        node = root->left;
        rightLenth = 1;
        for(; node->right != nullptr; node = node->right, rightLenth++);
        if(leftLenth - 1 == rightLenth){
            //说明左边是满二叉树
            return pow(2, rightLenth) - 1 + 1 + countNodes(root->right);
        }
        else{
            //右边是满的
            return pow(2, rightLenth) - 1 + 1 + countNodes(root->left);
        }
        
    }
};
 
虽然写出来了，但是自己写这种递归还是没有太多的条理。
 
比如递归基的写法：这里就是要么直接到空了，要么就是完美二叉树了直接反弹上去就得了！还有就是对于一般情况下的处理就是完全二叉树，反正总有点感觉不是那么的清晰熟练！
 
class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        int leftHeight = 0, rightHeight = 0; // 这里初始为0是有目的的，为了下面求指数方便
        while (left) {  // 求左子树深度
            left = left->left;
            leftHeight++;
        }
        while (right) { // 求右子树深度
            right = right->right;
            rightHeight++;
        }
        if (leftHeight == rightHeight) {
            return (2 << leftHeight) - 1; // 注意(2<<1) 相当于2^2，所以leftHeight初始为0
        }
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};代码随想录的答案
 
有两个点要学习，第一个就是对于<<运算符的使用，左移多少相当于乘以多少个二。
 
另外一个就是他在整完两个递归基之后对于一般的情况直接是用的递归，而我还傻乎乎的在判断了一波，也就是递归没有写彻底。
 
另外一个骚气的方法就是：首先前n-1层一定是满的二叉树，你只需要摸清最后一层到哪开始没有的，那么难点就是在于摸清最后一层的个数，这个思路我之前也有过，但是由于不会摸清那玩意就没有实现出来。
 
 
 
 
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;
        }
        int low = 1 << level, high = (1 << (level + 1)) - 1;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (exists(root, level, mid)) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }

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

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/count-complete-tree-nodes/solution/wan-quan-er-cha-shu-de-jie-dian-ge-shu-by-leetco-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 
 涉及到位运算，没看懂，以后再说！
 
 
 整体思路说一下，就是利用这个骚气的位运算：把第几个元素中的几能转换成0和1表示左右最终表示出从根节点到第几个节点的路径，这样就泥马的一步到位的去访问 第几个元素。所以你就利用二分不断缩小查找的范围，找到最后一个节点位置！