欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

已知一棵完全二叉树,求其节点的个数。要求:时间复杂度低于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的满二叉树 在递归求解左子树部分
 }