当前位置:网站首页>判斷二叉樹是否為完全二叉樹
判斷二叉樹是否為完全二叉樹
2022-07-05 23:01: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!");
}
}
边栏推荐
- openresty ngx_ Lua request response
- Nacos installation and service registration
- leecode-学习笔记
- Hcip day 11 (BGP agreement)
- 2022 R2 mobile pressure vessel filling review simulation examination and R2 mobile pressure vessel filling examination questions
- Global and Chinese markets of tantalum heat exchangers 2022-2028: Research Report on technology, participants, trends, market size and share
- Douban scoring applet Part-2
- Ultrasonic sensor flash | LEGO eV3 Teaching
- Expectation, variance and covariance
- I closed the open source project alinesno cloud service
猜你喜欢
Error when LabVIEW opens Ni instance finder
My experience and summary of the new Zhongtai model
Alibaba Tianchi SQL training camp task4 learning notes
Usage Summary of scriptable object in unity
Starting from 1.5, build a micro Service Framework -- log tracking traceid
Masked Autoencoders Are Scalable Vision Learners (MAE)
两数之和、三数之和(排序+双指针)
Metasploit (MSF) uses MS17_ 010 (eternal blue) encoding:: undefined conversionerror problem
Hcip day 11 (BGP agreement)
链表之双指针(快慢指针,先后指针,首尾指针)
随机推荐
February 13, 2022-4-symmetric binary tree
东南亚电商指南,卖家如何布局东南亚市场?
Global and Chinese markets for children's amusement facilities 2022-2028: Research Report on technology, participants, trends, market size and share
Nacos installation and service registration
First, redis summarizes the installation types
LeetCode145. Post order traversal of binary tree (three methods of recursion and iteration)
Exponential weighted average and its deviation elimination
Nacos 的安装与服务的注册
Paddle Serving v0.9.0 重磅发布多机多卡分布式推理框架
Getting started stm32--gpio (running lantern) (nanny level)
Methods modified by static
Double pointer of linked list (fast and slow pointer, sequential pointer, head and tail pointer)
Registration and skills of hoisting machinery command examination in 2022
2022 R2 mobile pressure vessel filling review simulation examination and R2 mobile pressure vessel filling examination questions
513. Find the value in the lower left corner of the tree
30 optimization skills about mysql, super practical
分布式解决方案之TCC
Lesson 1: serpentine matrix
Boring boring
分布式解决方案选型