给定一棵二叉树的根节点，判断这棵二叉树是否为满二叉树。
满二叉树：如果树的高度是 h h h，则节点数一定是 2 h − 1 2^h - 1 2h−1。
所以根据二叉树的递归套路：假设X为根节点的树，向左右子树收集两个信息：高度 h h h 和 节点数 n n n，判断是否满足满二叉树的条件。
另外，如果左树是满二叉树，右树是满二叉树，且左右树的高度一致，那么整棵树是满二叉树。
所以，也可以利用二叉树的递归套路，从左右树获取信息：（1）是否为满二叉树 （2）高度
/*************************************************************************
> File Name: 036.判断二叉树是否为满二叉树.cpp
> Author: Maureen
> Mail: Maureen@qq.com
> Created Time: 五 7/ 1 16:37:02 2022
************************************************************************/
#include <iostream>
#include <ctime>
using namespace std;
class TreeNode {
public:
int value;
TreeNode *left;
TreeNode *right;
TreeNode(int data) : value(data) {}
};
//方法1：收集整棵树的高度和节点数
//只有满二叉树满足：2^h - 1 == n
class Info1 {
public:
int height;//高度
int nodeCnt;//节点数
Info1(int h, int c) : height(h), nodeCnt(c) {}
};
Info1 *process1(TreeNode *x) {
if (x == nullptr) {
return new Info1(0, 0);
}
Info1 *leftInfo = process1(x->left);
Info1 *rightInfo = process1(x->right);
int height = max(leftInfo->height, rightInfo->height) + 1;
int nodeCnt = leftInfo->nodeCnt + rightInfo->nodeCnt + 1;
return new Info1(height, nodeCnt);
}
bool isFullBT1(TreeNode *root) {
if (root == nullptr) return true;
Info1 *info = process1(root);
return (1 << info->height) - 1 == info->nodeCnt;
}
//方法2: 收集 子树是否满二叉树 和 子树高度
//左树满 && 右树满 && 左树高度和右树高度一样，那么整棵树就是满的
class Info2 {
public:
bool isFull;
int height;
Info2(bool isfull, int h) : isFull(isfull), height(h) {}
};
Info2 *process2(TreeNode *x) {
if (x == nullptr) {
return new Info2(true, 0);
}
Info2 *leftInfo = process2(x->left);
Info2 *rightInfo = process2(x->right);
int height = max(leftInfo->height, rightInfo->height) + 1;
bool isFull = leftInfo->isFull && rightInfo->isFull && leftInfo->height == rightInfo->height;
return new Info2(isFull, height);
}
bool isFullBT2(TreeNode *root) {
return process2(root)->isFull;
}
//for test
TreeNode *generate(int level, int maxl, int maxv) {
if (level > maxl || (rand() % 100 / (double)101) < 0.5)
return nullptr;
TreeNode *root = new TreeNode(rand() % maxv);
root->left = generate(level + 1, maxl, maxv);
root->right = generate(level + 1, maxl, maxv);
return root;
}
TreeNode *generateRandomBST(int level, int value) {
return generate(1, level, value);
}
int main() {
srand(time(0));
int level = 5;
int value = 100;
int testTimes = 1000001;
cout << "Test begin:" << endl;
for (int i = 0; i < testTimes; i++) {
TreeNode *root = generateRandomBST(level, value);
if (isFullBT1(root) != isFullBT2(root)) {
cout << "Failed!" << endl;
return 0;
}
}
cout << "Success!" << endl;
return 0;
}
public class isFullBT {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
// 第一种方法
// 收集整棵树的高度h，和节点数n
// 只有满二叉树满足 : 2 ^ h - 1 == n
public static boolean isFull1(Node head) {
if (head == null) {
return true;
}
Info1 all = process1(head);
return (1 << all.height) - 1 == all.nodes;
}
public static class Info1 {
public int height; //高度
public int nodes; //节点数
public Info1(int h, int n) {
height = h;
nodes = n;
}
}
public static Info1 process1(Node head) {
if (head == null) {
return new Info1(0, 0);
}
Info1 leftInfo = process1(head.left);
Info1 rightInfo = process1(head.right);
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
int nodes = leftInfo.nodes + rightInfo.nodes + 1;
return new Info1(height, nodes);
}
// 第二种方法
// 收集子树是否是满二叉树
// 收集子树的高度
// 左树满 && 右树满 && 左右树高度一样 -> 整棵树是满的
public static boolean isFull2(Node head) {
if (head == null) {
return true;
}
return process2(head).isFull;
}
public static class Info2 {
public boolean isFull;
public int height;
public Info2(boolean f, int h) {
isFull = f;
height = h;
}
}
public static Info2 process2(Node h) {
if (h == null) {
return new Info2(true, 0);
}
Info2 leftInfo = process2(h.left);
Info2 rightInfo = process2(h.right);
boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
return new Info2(isFull, height);
}
// for test
public static Node generateRandomBST(int maxLevel, int maxValue) {
return generate(1, maxLevel, maxValue);
}
// for test
public static Node generate(int level, int maxLevel, int maxValue) {
if (level > maxLevel || Math.random() < 0.5) {
return null;
}
Node head = new Node((int) (Math.random() * maxValue));
head.left = generate(level + 1, maxLevel, maxValue);
head.right = generate(level + 1, maxLevel, maxValue);
return head;
}
public static void main(String[] args) {
int maxLevel = 5;
int maxValue = 100;
int testTimes = 1000000;
System.out.println("测试开始");
for (int i = 0; i < testTimes; i++) {
Node head = generateRandomBST(maxLevel, maxValue);
if (isFull1(head) != isFull2(head)) {
System.out.println("出错了!");
}
}
System.out.println("测试结束");
}
}