给定一棵二叉树的根节点root，判断这棵树是否为完全二叉树。
完全二叉树就是每一层要么是满的，如果不满也是从左到右依次变满。
按层遍历，遵循几个原则：
目标：X 为头的二叉树是否为完全二叉树；
可能性：分类——最后一层的最后一个节点到哪儿了
① 最后一层节点是满的：如果左树是满的，右树也是满的，且左右树高度一致，则以 X 为头的这棵二叉树一定是完全二叉树。（左树满，右树满，左高 = 右高）
②最后一层节点不满：
1) 最后一个节点在左树，但是左树没满：如果左树是完全二叉树，且右树是满的，且左树比右树高度大1，那么 X 为头的这棵二叉树一定是完全二叉树。（左完全，右满，左高 = 右高 + 1）
2）最后一个节点刚好使得左树满：左树是满的，右树是满的，左树高度比右树高度大1，那么 X 为头的这棵二叉树一定是完全二叉树。（左满，右满，左高 = 右高+ 1）
3）最后一个节点在右树上，但是右树没满：左树是满的，右树是完全二叉树，且左右树高度一致，那么 X 为头的这棵二叉树一定是完全二叉树。（左满，右完全，左高 = 右高）
为了支持这 4 种可能性，需要向左右树收集的信息：（1）是否是满二叉树；（2）是否是完全二叉树；（3）高度。
/*************************************************************************
> File Name: 041.判断二叉树是否为完全二叉树.cpp
> Author: Maureen
> Mail: Maureen@qq.com
> Created Time: 一 7/ 4 19:39:10 2022
************************************************************************/
#include <iostream>
#include <ctime>
#include <queue>
using namespace std;
class TreeNode {
public:
int value;
TreeNode *left;
TreeNode *right;
TreeNode(int data) : value(data) {}
};
//方法一：经典做法
bool isCBT1(TreeNode *root) {
if (root == nullptr) return true;
queue<TreeNode*> _que;
bool leaf = true;
TreeNode *l = nullptr;
TreeNode *r = nullptr;
_que.push(root);
while (!_que.empty()) {
root = que.front();
que.pop();
l = root->left;
r = root->right;
//遇到了不双全的节点且发现当前节点不是叶节点 或 有右孩子无左孩子
if (leaf && (l != nullptr || r != nullptr)) || (l == nullptr && r != nullptr) ) {
return false;
}
if (l != nullptr) {
_que.push(l);
}
if (r != nullptr) {
_que.push(r);
}
if (l == nullptr || r == nullptr) { //只有一个孩子，就是孩子不双全的情况
leaf = true;
}
}
return true;
}
//方法二：二叉树的递归套路
class Info {
public:
bool isFull;
bool isCBT;
int height;
Info(bool full, bool cbt, int h) :
isFull(full), isCBT(cbt), height(h) {}
};
Info *process(TreeNode *x) {
if (x == nullptr) {
retur new Info(true, true, 0);
}
Info *leftInfo = process(x->left);
Info *rightInfo = process(x->right);
int height = max(leftInfo->height, rightInfo->height) + 1；
bool isFull = leftInfo->isFull && rightInfo->isFull && leftInfo->height == rightInfo->height;
bool isCBT = false;
//可能性1：左满，右满，左高 = 右高
if (leftInfo->isFull && rightInfo->isFull && leftInfo->height == rightInfo->height) {
isCBT = true;
} else if (leftInfo->isCBT && rightInfo->isFull && leftInfo->height == rightInfo->height + 1) { //可能性2：左完全，右满，左高 = 右高 + 1
isCBT = true;
} else if (leftInfo->isFull && rightInfo->isFull && leftInfo->height == rightInfo->height + 1) { //可能性3：左满，右满，左高 = 右高 + 1
isCBT = true;
} else if (leftInfo->isFull && right->isCBT && leftInfo->height == rightInfo->height) { //可能性4：左满，右完全，左高 = 右高
isCBT = true;
}
return new Info(isFull, isCBT, height);
}
bool isCBT2(TreeNode *root) {
return process(root)->isCBT;
}
//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 maxLevel = 4;
int maxValue = 100;
int testTimes = 1000001;
cout << "Test begin:" << endl;
for (int i = 0; i < testTimes; i++) {
TreeNode *root = generateRandomBST(maxLevel, maxValue);
if (isCBT1(root) != isCBT2(root)) {
cout << "Failed!" << endl;
return 0;
}
if (i && i % 1000 == 0) cout << i << " cases passed!" << endl;
}
cout << "Success!!" << endl;
return 0;
}
import java.util.LinkedList;
public class IsCBT {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
//经典做法
public static boolean isCBT1(Node head) {
if (head == null) {
return true;
}
LinkedList<Node> queue = new LinkedList<>();
// 是否遇到过左右两个孩子不双全的节点
boolean leaf = false;
Node l = null;
Node r = null;
queue.add(head);
while (!queue.isEmpty()) {
head = queue.poll();
l = head.left;
r = head.right;
if (
// 如果遇到了不双全的节点之后，又发现当前节点不是叶节点
(leaf && (l != null || r != null))
||
(l == null && r != null) //有右无左的情况
) {
return false;
}
if (l != null) {
queue.add(l);
}
if (r != null) {
queue.add(r);
}
if (l == null || r == null) { //如果只存在一个孩子或没有孩子，就是遇到了孩子不双全的情况
leaf = true;
}
}
return true;
}
//递归套路的做法
public static boolean isCBT2(Node head) {
return process(head).isCBT;
}
public static class Info {
public boolean isFull; //是否满的
public boolean isCBT;// 是否完全二叉树
public int height; //高度
public Info(boolean full, boolean cbt, int h) {
isFull = full;
isCBT = cbt;
height = h;
}
}
public static Info process(Node x) {
if (x == null) { //空树的设置
return new Info(true, true, 0);
}
Info leftInfo = process(x.left);
Info rightInfo = process(x.right);
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
//左右树都是满的，且高度一致，就是满二叉树
boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
boolean isCBT = false;
//可能性1：左右树都是满的，且高度一致
if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height) {
isCBT = true;
}
//可能性2：左树是完全，右树是满的，左树比右树高1
else if (leftInfo.isCBT && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
isCBT = true;
}
//可能性3：左树是满的，右树是满的，左树比右树高1
else if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
isCBT = true;
}
//可能性4：左树是满的，右数是完全，左右树高度一致
else if (leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height) {
isCBT = true;
}
return new Info(isFull, isCBT, 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;
for (int i = 0; i < testTimes; i++) {
Node head = generateRandomBST(maxLevel, maxValue);
if (isCBT1(head) != isCBT2(head)) {
System.out.println("Oops!");
}
}
System.out.println("finish!");
}
}