已知一棵完全二叉树,求其节点的个数。要求:时间复杂度低于O(N),N为这棵树的节点个数
程序员文章站
2022-05-16 10:08:31
...
///已知一棵完全二叉树,求其节点的个数
//给根据二叉树的性质,二叉树的结点个数=2^k - 1;k为二叉树的高度
//遍历当前结点左子树最深处,就是二叉树高度(因为完全二叉树是从左边开始堆砌的)
//再遍历当前结点右子树的左子树最深处,判断是否到达了k
//如果达到了k,那么右子树也是满二叉树,递归右子树
//如果未达到k。那么右子树是高度小于左子树的满二叉树,直接公式
class TreeNode
{
public:
int val;
TreeNode*left;
TreeNode* right;
TreeNode(int x) {
this->val = val;
this->left = NULL;
this->right = NULL;
}
};
typedef class TreeNode *Tree;
//计算树深度
int Depth(Tree head,int level )//level表示当前所在层数
{
if (head == NULL)
return 0;
int L;
while (head != NULL)
{
L++;
head = head->left;
}
return L - 1;
}
int NodeNum(Tree head, int level, int h)//h代表树的深度
{
if (level == h)//当前在最后一层
return 1;
if ((Depth(head->right, level + 1) == h)//右子树到达最深边界了,右子树的左子树也是满的
return (1 << (h-level))+ NodeNum(head->right,level+1,h);
else
return (1<<(h-level-1))+NodeNum(head->left,level+1,h);//右子树没有到边界,那右子树
//就是比左子树高度要小1的满二叉树 在递归求解左子树部分
}
上一篇: 已知一棵完全二叉树求其节点的个数
下一篇: 已知一棵完全二叉树,求其节点的个数