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

题目

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 个节点。

示例 1：

输入：root = [1,2,3,4,5,6]
输出：6

示例 2：

输入：root = []
输出：0

示例 3：

输入：root = [1]
输出：1

解答 & 代码

二分查找 + 位运算：

1. 计算二叉树的高度 height（从根节点到最左边叶子节点的路径长度，而不是节点数）
2. 二分查找确定完全二叉树的节点数：
   1. 初始查找范围，即最后一层的节点编号范围
   2. 每次查找取 mid，如果编号为 mid 的节点存在，则令 left = mid + 1；否则令 right = mid - 1，来收缩查找范围
   3. 最终查找结束， **right** 就是完全二叉树最后一个结点的编号，也就是完全二叉树的节点数

      • 层号 h 从 0 开始记，最后一层就是第 height 层。
      • 节点编号从 1 开始记，第 h 层（假设节点是满的）的节点编号为
      • 完全二叉树的节点数就是最后一层的最后一个结点的编号

问题转化为：如何判定编号为 k 的节点是否存在？

• 如果节点 k 位于第 h 层，那么编号 k 可以表示为 h+1 位的二进制编码，其中最高位为 1，从高到低的其余各位代表从根节点到节点 k 的路径，0 表示移动到左子节点，1 表示移动到右子节点
• 因此通过位运算移动到第 h 层，即可判断节点 k 是否存在

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    // 计算二叉树的高度 height（从根节点到最左边叶子节点的路径长度，而不是节点数）
    int calHeight(TreeNode* root)
    {
        if(root == nullptr)
            return 0;
        int height = 0;
        while(root->left != nullptr)
        {
            ++height;
            root = root->left;
        }
        return height;
    }
    // 判断编号为 k 的节点是否存在
    bool existNodeK(TreeNode* root, int k, int height)
    {
        TreeNode* node = root;
        int bit = 1 << (height - 1);
        for(int i = 0; i < height; ++i)
        {
            if((k & bit) == 0)
                node = node->left;
            else
                node = node->right;
            bit = bit >> 1;
        }
        return node != nullptr;
    }
public:
    int countNodes(TreeNode* root) {
        if(root == nullptr)
            return 0;
        // 1. 计算二叉树的高度 height（从根节点到最左边叶子节点的路径长度，而不是节点数）
        int height = calHeight(root);
        if(height == 0)
            return 1;
        // 2. 二分查找完全二叉树的节点数（即查找第 height 层最后一个非空的节点的编号）
        int left = pow(2, height);                // 第 height 层第 1 个节点的编号
        int right = pow(2, height + 1) - 1;        // 第 height 层最后一个节点的编号（可能不存在）
        while(left <= right)
        {
            int mid = left + (right - left) / 2;
            bool existMid = existNodeK(root, mid, height);    // 判断编号 mid 的节点是否存在
            if(existMid == true)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return right;
    }
};

复杂度分析：设二叉树节点数为 n

• 时间复杂度 ：
  • 统计二叉树的高度：时间复杂度 O(height) = O(log n)
  • 二分查找确定二叉树结点个数：最后一层最多个节点，也就是说二分查找最初的查找范围为个节点，因此二分查找的次数为；而每次二分查找，需要访问一条从根节点到最后一层的路径，来判断 mid 节点是否存在，时间复杂度 O(height)。因此整体的时间复杂度为
• 空间复杂度 O(1)：

执行结果：

执行结果：通过
执行用时：28 ms, 在所有 C++ 提交中击败了 72.33% 的用户
内存消耗：30.2 MB, 在所有 C++ 提交中击败了 32.06% 的用户