完全二叉树结点个数公式 + 二分搜索

222. 完全二叉树的节点个数 - 力扣（LeetCode）

1. 先找深度搜索最左节点获得深度
2. 根据深度公式获得最后一层序列的范围[2^(h-1) , 2^h-1]，注意深度depth是从0还是1开始
3. 对该范围进行二分查找，判断当前mid结点编号（也就是第几个结点）是否存在（isexist()）,这里要注意出循环了仍然不知道最后一个结点是存在还是不存在，所以要再判断一次isexist才能确定最右的叶子节点是不是最后的mid
4. 对于isexist（）:判断当前叶子结点是否存在的问题，可以利用完全二叉树的性质，根节点为1，左孩子追加0，右孩子追加1，以此类推，正好可以对应上结点的编号。反过来，只要对编号按二进制确定路径就可以找到其结点是否存在了。

时间复杂度优化至 l o g n logn logn

    class Solution {
    public:
        bool isexist(TreeNode* root, int depth, int val) {
            if (depth < 1) return root->val == val;
            int bits = val;
            TreeNode* tmp = root;
            while (depth--){
                if (1<right;
                else tmp = tmp->left;
            }
            if (!tmp) return false;
            return true;
        }
        int countNodes(TreeNode* root) {
            if (!root) return 0;
            int ans;
            int depth = -1;
            TreeNode* cur = root;
            while (cur) {
                cur = cur->left;
                depth++;
            }
            int l = 1 << depth, r = (1<<(depth+1)) - 1;
            int m = l;
            while(l <= r) {
                m = l + (r - l) / 2;
                if (isexist(root,depth,m)) {
                    l = m + 1;
                }
                else{
                    r = m - 1;
                }
            }
            if (isexist(root,depth,m)) return m;
            return m - 1;
        }
    };
    ```