当前位置:网站首页>判断二叉树是否为完全二叉树
判断二叉树是否为完全二叉树
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)
Registration of Electrical Engineering (elementary) examination in 2022 and the latest analysis of Electrical Engineering (elementary)
Activate function and its gradient
透彻理解JVM类加载子系统
How can easycvr cluster deployment solve the massive video access and concurrency requirements in the project?
SPSS analysis of employment problems of college graduates
Nanjing: full use of electronic contracts for commercial housing sales
从 1.5 开始搭建一个微服务框架——日志追踪 traceId
Lesson 1: serpentine matrix
我把开源项目alinesno-cloud-service关闭了
随机推荐
我对新中台模型的一些经验思考总结
Metaverse ape ape community was invited to attend the 2022 Guangdong Hong Kong Macao Great Bay metauniverse and Web3.0 theme summit to share the evolution of ape community civilization from technology
openresty ngx_ Lua request response
南京:全面启用商品房买卖电子合同
[speech processing] speech signal denoising and denoising based on Matlab GUI low-pass filter [including Matlab source code 1708]
Leetcode daily question 1189 The maximum number of "balloons" simple simulation questions~
Why does the C# compiler allow an explicit cast between IEnumerable&lt; T&gt; and TAlmostAnything?
The difference between MVVM and MVC
从 1.5 开始搭建一个微服务框架——日志追踪 traceId
Tensor attribute statistics
513. Find the value in the lower left corner of the tree
查看网页最后修改时间方法以及原理简介
a-tree 树的全部展开和收起
Selenium+Pytest自动化测试框架实战
Marginal probability and conditional probability
记录几个常见问题(202207)
Usage Summary of scriptable object in unity
Nacos 的安装与服务的注册
我把开源项目alinesno-cloud-service关闭了
Ieventsystemhandler event interface