完全二叉树节点个数

问题

给定一棵完全二叉树的头节点 head,求其中的节点个数。
时间复杂度不超过O(n)

完全二叉树与满二叉树

思路

遍历一颗二叉树，即可得到树中节点个数，但它的时间复杂度为O(n).怎样才能将复杂度降到不超过O(n)呢

完全二叉树介绍

一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树（Complete Binary Tree）。深度为k的完全二叉树，至少有 2^(k - 1)个节点，至多有2^k - 1个节点

由完全二叉树的结构特点出发，我们不难想到以下算法：从根结点开始向下用公式计算为其满二叉子树的节点个数，再递归处理其另一侧完全二叉子树的结点总数，故完全二叉树节点个数等于满二叉子树的节点数 + 1(父节点) + 完全二叉子树的节点数

根据上面的算法描述可知，要求得完全二叉子树节点数，必须从根结点向下，每一层递归执行一遍，直到树底结束。故时间复杂度为O(logN)*O(logN),即 O((logN)^2)

定义一个level变量记录当前所在层数，当level到达完全二叉树的树高h时，即为递归出口。其中level通过传参的方式，随着递归不断地增大。

struct treeNode
{
    int data;
    treeNode *l;
    treeNode *r;

    public: treeNode(int data)
    {
        this->data = data;
    }
};

//最左结点的高度, 注意返回高度时要减1
int mostLeftLevel(treeNode *node, int level)
{
    while (node != NULL)
    {
        level++;
        node = node->l;
    }
    return level - 1;
}

int nodeNum(treeNode *head, int level, int h)
{
    if (head == NULL)
    {
        return 0;
    }
    if (level == h)
    {
        return 1;
    }
    if (mostLeftLevel(head->r, level + 1) == h)
    {
        return (1 << (h - level)) + nodeNum(head->r, level + 1, h);
    }
    else
    {
        return (1 << (h - level - 1)) + nodeNum(head->l, level + 1, h);
    }
    return 0;
}

int main()
{
    treeNode *t1 = new treeNode(1);
    treeNode *t2 = new treeNode(2);
    treeNode *t3 = new treeNode(3);
    treeNode *t4 = new treeNode(4);
    treeNode *t5 = new treeNode(5);
    treeNode *t6 = new treeNode(6);
    t1->l = t2; t1->r = t3;
    t2->l = t4; t2->r = t5;
    t3->l = t6;
    cout << nodeNum(t1, 1, mostLeftLevel(t1, 1)) << endl;
}

C++方式写树节点结构，以及建树的过程比起C还是漂亮不少