问题
给定一棵完全二叉树的头节点 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还是漂亮不少