当前位置：网站首页>判断二叉树是否为完全二叉树
判断二叉树是否为完全二叉树
2022-07-05 22:50:00 【明朗晨光】
1、题目
给定一棵二叉树的根节点root，判断这棵树是否为完全二叉树。
2、分析
完全二叉树就是每一层要么是满的，如果不满也是从左到右依次变满。
经典做法
按层遍历，遵循几个原则：
- 如果某个节点有右孩子，没有左孩子，则它一定不是完全二叉树；
- 当第一次遇到左右孩子不双全的时候，剩下遍历的节点必须是叶节点，否则不是完全二叉树。
递归套路
目标：X 为头的二叉树是否为完全二叉树；
可能性：分类——最后一层的最后一个节点到哪儿了
① 最后一层节点是满的：如果左树是满的，右树也是满的，且左右树高度一致，则以 X 为头的这棵二叉树一定是完全二叉树。（左树满，右树满，左高 = 右高）
②最后一层节点不满：
1) 最后一个节点在左树，但是左树没满：如果左树是完全二叉树，且右树是满的，且左树比右树高度大1，那么 X 为头的这棵二叉树一定是完全二叉树。（左完全，右满，左高 = 右高 + 1）
2）最后一个节点刚好使得左树满：左树是满的，右树是满的，左树高度比右树高度大1，那么 X 为头的这棵二叉树一定是完全二叉树。（左满，右满，左高 = 右高+ 1）
3）最后一个节点在右树上，但是右树没满：左树是满的，右树是完全二叉树，且左右树高度一致，那么 X 为头的这棵二叉树一定是完全二叉树。（左满，右完全，左高 = 右高）为了支持这 4 种可能性，需要向左右树收集的信息：（1）是否是满二叉树；（2）是否是完全二叉树；（3）高度。
3、实现
C++ 版
/************************************************************************* > File Name: 041.判断二叉树是否为完全二叉树.cpp > Author: Maureen > Mail: [email protected] > 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;
}
Java 版
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!");
}
}
边栏推荐
- 【Note17】PECI（Platform Environment Control Interface）
- Marginal probability and conditional probability
- 二叉树（二）——堆的代码实现
- 链表之双指针（快慢指针，先后指针，首尾指针）
- 30 optimization skills about mysql, super practical
- Why does the C＃ compiler allow an explicit cast between IEnumerable＆lt; T＆gt; and TAlmostAnything?
- Postman core function analysis - parameterization and test report
- 记录几个常见问题(202207)
- Metasploit (MSF) uses MS17_ 010 (eternal blue) encoding:: undefined conversionerror problem
- audiopolicy
猜你喜欢
【Note17】PECI（Platform Environment Control Interface）
Metaverse ape received $3.5 million in seed round financing from negentropy capital
TCC of distributed solutions
Commonly used probability distributions: Bernoulli distribution, binomial distribution, polynomial distribution, Gaussian distribution, exponential distribution, Laplace distribution and Dirac delta d
Nangou Gili hard Kai font TTF Download with installation tutorial
VOT Toolkit环境配置与使用
南京：全面启用商品房买卖电子合同
第十七周作业
Vcomp110.dll download -vcomp110 What if DLL is lost
Selenium+Pytest自动化测试框架实战
随机推荐
视频标准二三事
Evolution of APK reinforcement technology, APK reinforcement technology and shortcomings
The code generator has deoptimised the styling of xx/typescript. js as it exceeds the max of 500kb
我对新中台模型的一些经验思考总结
MCU case -int0 and INT1 interrupt count
Hcip day 11 (BGP agreement)
Navigation day answer applet: preliminary competition of navigation knowledge competition
Expectation, variance and covariance
分布式解决方案选型
PLC编程基础之数据类型、变量声明、全局变量和I/O映射（CODESYS篇 )
The introduction to go language is very simple: String
Distributed resource management and task scheduling framework yarn
Simple and beautiful method of PPT color matching
Arduino 测量交流电流
Starting from 1.5, build a micro Service Framework -- log tracking traceid
Ieventsystemhandler event interface
Registration of Electrical Engineering (elementary) examination in 2022 and the latest analysis of Electrical Engineering (elementary)
二叉树（二）——堆的代码实现
Double pointer of linked list (fast and slow pointer, sequential pointer, head and tail pointer)
一文搞定class的微觀結構和指令