完全二叉树的节点个数

Q

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

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

示例 1：

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

示例 2：

输入：root = []
输出：0

示例 3：

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

提示：

• 树中节点的数目范围是[0, 5 * 104]
• 0 <= Node.val <= 5 * 104
• 题目数据保证输入的树是 完全二叉树

进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？

A

最简单的就是直接遍历整棵树（BFS或DFS）累计节点个数

不过我们可以利用完全二叉树的结构性质

利用完全二叉树性质时，取根所处深度为0而不是1会让分析简单一些

1. 计算空结点数目，右深树

最坏为O(n)，即最底下一层只有一个节点，实际上只会经过包含所有空结点的最小的树（以及从根节点按右边走到这棵树的根）

class Solution
{
    int h;

public:
    // return done: done means that, we have found the last empty node, there's no more empty node
    // accumulate empty_node_count
    bool count_empty_node_for_level_just_above_leaf(TreeNode *root, int depth, int &empty_node_cnt)
    {
        if (depth + 1 == h)
        {
            if (root->left)
            {
                if (root->right == nullptr)
                    empty_node_cnt++;
                return true;
            }
            empty_node_cnt += 2;
            return false;
        }
        else
        {
            if (count_empty_node_for_level_just_above_leaf(root->right, depth + 1, empty_node_cnt))
                return true;
            return count_empty_node_for_level_just_above_leaf(root->left, depth + 1, empty_node_cnt);
        }
    }
    int countNodes(TreeNode *root)
    {
        if (root == nullptr)
            return 0;
        // calculate h
        h = -1;
        TreeNode *p = root;
        while (p)
        {
            p = p->left;
            ++h;
        }
        // calculate node
        if (h == 0)
            return 1;
        int empty_node_count = 0;
        count_empty_node_for_level_just_above_leaf(root, 0, empty_node_count);
        return (1 << (h + 1)) - empty_node_count - 1;
        // last level: (1 << h) - empty_node_count
        // above levels: (1 << h) - 1
    }
};

2. 二分查找，完全二叉树的节点若从1开始编号，编号的二进制表示代表了从根到该节点的路径

第i层的节点的编号二进制有i+1位，最高位是1，其余位从高到低表示从根走到该节点的路径：0则向左，1则向右

O(logn*logn)，对宽度为2^h的范围进行二分查找，判断次数是log(2^h)=h=logn（一定会判断这么多次，因为要到l和r相遇才结束），每次判断都是按比特指示从根走到最下层，复杂度是logn，因此logn*logn

class Solution
{
public:
    // num: `h`th bit is 1; other bits: from high bit to low bit, the path from root to node
    bool node_exist(TreeNode *root, int num, int h)
    {
        int msk = 1 << (h - 1);
        for (int i = 0; i < h; ++i)
        {
            if (msk & num)
            {
                // go right
                if (root->right)
                    root = root->right;
                else
                    return false;
            }
            else
            {
                // go left
                if (root->left)
                    root = root->left;
                else
                    return false;
            }
            msk >>= 1;
        }
        return true;
    }
    int countNodes(TreeNode *root)
    {
        if (root == nullptr)
            return 0;
        // get height
        int h = -1;
        TreeNode *p = root;
        while (p)
        {
            ++h;
            p = p->left;
        }
        if (h == 0)
            return 1;
        // binary search for node_count: whether node_count is mid?
        // number the node from 1 (start from root, then level by level, each level from left to right)
        // then node's id represents path from root, also id somewhat represents count of nodes

        // [l, r)
        // "l is inclusive, r is exclusive" is from the following process. see comments below

        // #nodes above level h: (1 << h) - 1
        int l = 1 << h;       // lower bound of node_count: level h only contain one node
        int r = 1 << (h + 1); // upper bound of node_count: level h is full: 1 << h
        int mid;
        while (l + 1 < r)
        {
            mid = (l + r) / 2;
            if (node_exist(root, mid, h))
                // #nodes >= mid
                l = mid; // l is inclusive
            else
                // #nodes < mid
                r = mid; // r is exclusive
        }
        return l;
    }
};
// @lc code=end

3. 比较左右两边的depth

复杂度不太行，不过有这个思路

好的地方可能在，比如在某节点，左子树没有空节点，那么对左子树的调用就会一层结束

class Solution
{
public:
    int countNodes(TreeNode *root)
    {
        if (root == nullptr)
            return 0;
        TreeNode *p;
        // left height
        int lh = -1;
        p = root;
        while (p)
        {
            ++lh;
            p = p->left;
        }
        // right height
        int rh = -1;
        p = root;
        while (p)
        {
            ++rh;
            p = p->right;
        }
        
        if (lh == rh)
            // all level is full
            // 2^0 + ... + 2^lh: from binary representation point of view, this sum = (1 << (lh + 1)) - 1
            return (1 << (lh + 1)) - 1;
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
};
// @lc code=end

最坏为O(nlogn)，即最底下一层只有一个节点，需要求logn层的左右两边depth（logn次，因为树高是logn），

对第i层求depth的复杂度：第i层每个节点都求左右两边的depth，第i层有节点2^i个，求depth的复杂度是logn-i（树的深度-当前层的深度），所以是2^i*(logn-i)，

然后对i从0到logn求和，得到nlogn