判断是否为满二叉树(C++实现)_m0_58086930的博客

//判断是否为满二叉树(递归法)    (结点个数n=2^h-1)
/*
step:   1)先求该书=树的最大深度h
		2)再求结点总个数n
		3)若n==2^h-1，则满
*/
class ReturnInfo {
public:
	int height;
	int no;//结点个数
	ReturnInfo(int h, int n) {
		height = h;
		no = n;
	}
};
bool isFBT(Node* head) {
	ReturnInfo info = process2(head);
	return info.no == (1 << info.height - 1);//左移h位相当于2的h次方
}
ReturnInfo process2(Node* head) {
	if (head == NULL)
		return ReturnInfo(0, 0);
	ReturnInfo leftInfo = process2(head->left);
	ReturnInfo rightInfo = process2(head->right);
	return ReturnInfo(max(leftInfo.height, rightInfo.height) + 1, leftInfo.no + rightInfo.no + 1);
}