当前位置:网站首页>Judge whether the binary tree is a complete binary tree
Judge whether the binary tree is a complete binary tree
2022-07-05 23:02:00 【Bright morning light】
1、 subject
Given the root node of a binary tree root
, Judge whether this tree is a complete binary tree .
2、 analysis
A complete binary tree means that each layer is either full , If dissatisfaction is also full from left to right .
Classic practice
Traverse layer by layer , Follow several principles :
- If a node has a right child , There is no left child , Then it must not be a complete binary tree ;
- When I first met a child who was not both right and left , The remaining traversal nodes must be leaf nodes , Otherwise, it is not a complete binary tree .
Recursive routine
The goal is :X Whether a binary tree with a head is a complete binary tree ;
possibility : classification —— Where is the last node on the last floor
① The last layer of nodes is full : If the left tree is full , The right tree is also full , And the height of the left and right trees is the same , with X The binary tree with the head must be a complete binary tree .( Zuo Shuman , The right tree is full , Left high = Right high )
② The last layer node is not satisfied :
1) The last node is in the left tree , But the left tree is not full : If the left tree is a complete binary tree , And the right tree is full , And the left tree is higher than the right tree 1, that X The binary tree with the head must be a complete binary tree .( Left perfect , Right full , Left high = Right high + 1)
2) The last node just makes the left tree full : The left tree is full , The right tree is full , The height of the left tree is higher than that of the right tree 1, that X The binary tree with the head must be a complete binary tree .( Zuo man , Right full , Left high = Right high + 1)
3) The last node is on the right tree , But the right tree is not full : The left tree is full , The right tree is a complete binary tree , And the height of the left and right trees is the same , that X The binary tree with the head must be a complete binary tree .( Zuo man , Right perfect , Left high = Right high )To support this 4 A possibility , The information that needs to be collected from the left and right trees :(1) Is it a full binary tree ;(2) Whether it is a complete binary tree ;(3) Height .
3、 Realization
C++ edition
/************************************************************************* > File Name: 041. Determine whether a binary tree is a complete binary tree .cpp > Author: Maureen > Mail: [email protected] > Created Time: One 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) {
}
};
// Method 1 : Classic practice
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;
// Encountered an incomplete node and found that the current node is not a leaf node or There are right children but no left children
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) {
// Only one child , It's the situation of incomplete children
leaf = true;
}
}
return true;
}
// Method 2 : Recursive routine of binary tree
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;
// possibility 1: Zuo man , Right full , Left high = Right high
if (leftInfo->isFull && rightInfo->isFull && leftInfo->height == rightInfo->height) {
isCBT = true;
} else if (leftInfo->isCBT && rightInfo->isFull && leftInfo->height == rightInfo->height + 1) {
// possibility 2: Left perfect , Right full , Left high = Right high + 1
isCBT = true;
} else if (leftInfo->isFull && rightInfo->isFull && leftInfo->height == rightInfo->height + 1) {
// possibility 3: Zuo man , Right full , Left high = Right high + 1
isCBT = true;
} else if (leftInfo->isFull && right->isCBT && leftInfo->height == rightInfo->height) {
// possibility 4: Zuo man , Right perfect , Left high = Right high
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 edition
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;
}
}
// Classic practice
public static boolean isCBT1(Node head) {
if (head == null) {
return true;
}
LinkedList<Node> queue = new LinkedList<>();
// Have you ever met a node with incomplete left and right children
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 (
// If you encounter incomplete nodes , It is also found that the current node is not a leaf node
(leaf && (l != null || r != null))
||
(l == null && r != null) // Whether there is right or left
) {
return false;
}
if (l != null) {
queue.add(l);
}
if (r != null) {
queue.add(r);
}
if (l == null || r == null) {
// If there is only one child or no child , It's the case of incomplete children
leaf = true;
}
}
return true;
}
// Recursive routine
public static boolean isCBT2(Node head) {
return process(head).isCBT;
}
public static class Info {
public boolean isFull; // Is it full
public boolean isCBT;// Is it a complete binary tree
public int height; // Height
public Info(boolean full, boolean cbt, int h) {
isFull = full;
isCBT = cbt;
height = h;
}
}
public static Info process(Node x) {
if (x == null) {
// Empty tree settings
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;
// The trees on both sides are full , And highly consistent , It's full of binary trees
boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
boolean isCBT = false;
// possibility 1: The trees on both sides are full , And highly consistent
if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height) {
isCBT = true;
}
// possibility 2: The left tree is completely , The right tree is full , The left tree is taller than the right 1
else if (leftInfo.isCBT && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
isCBT = true;
}
// possibility 3: The left tree is full , The right tree is full , The left tree is taller than the right 1
else if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
isCBT = true;
}
// possibility 4: The left tree is full , The right number is complete , The height of the left and right trees is the same
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!");
}
}
边栏推荐
- [untitled]
- Paddle Serving v0.9.0 重磅发布多机多卡分布式推理框架
- 媒体查询:引入资源
- Expectation, variance and covariance
- Starting from 1.5, build a micro Service Framework -- log tracking traceid
- Tensor attribute statistics
- 2022 R2 mobile pressure vessel filling review simulation examination and R2 mobile pressure vessel filling examination questions
- audiopolicy
- February 13, 2022 -5- maximum depth of binary tree
- Leetcode buys and sells stocks
猜你喜欢
d3dx9_ How to repair 31.dll_ d3dx9_ 31. Solution to missing DLL
Simple and beautiful method of PPT color matching
Hcip day 11 (BGP agreement)
一文搞定垃圾回收器
Overview of Fourier analysis
Three. JS VR house viewing
【无标题】
鏈錶之雙指針(快慢指針,先後指針,首尾指針)
CJ mccullem autograph: to dear Portland
How to quickly understand complex businesses and systematically think about problems?
随机推荐
Selenium+pytest automated test framework practice
Use the rewrite rule to rewrite all accesses to the a domain name to the B domain name
Error when LabVIEW opens Ni instance finder
Global and Chinese markets of tantalum heat exchangers 2022-2028: Research Report on technology, participants, trends, market size and share
The introduction to go language is very simple: String
一文搞定JVM的内存结构
Arduino measures AC current
Nail error code Encyclopedia
openresty ngx_lua请求响应
Registration of Electrical Engineering (elementary) examination in 2022 and the latest analysis of Electrical Engineering (elementary)
VIM tail head intercept file import
Three.js-01 入门
谷歌地图案例
CJ mccullem autograph: to dear Portland
Data type, variable declaration, global variable and i/o mapping of PLC programming basis (CoDeSys)
TOPSIS code part of good and bad solution distance method
TypeError: this. getOptions is not a function
Finally understand what dynamic planning is
如何快速理解复杂业务,系统思考问题?
实现反向代理客户端IP透传