数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究统计二叉树中值都为 1 的节点组成的层数
二叉树是一种每个节点最多有两个子节点的树。给定一个二叉树，其节点值仅为 0 和 1。我们需要找到二叉树中至少包含一个 1 且所有 1 都连续存在的层数。
示例
让我们借助示例来理解：
输入
0 / \ 1 0 / \ / \ 1 1 0 0
输出
2
解释
第二层和第三层的所有 1 都位于连续的位置。
对于第 1 层，我们有 − 0（没有 1）
对于第 2 层，我们有 − 1 0（只有一个 1）
对于第 3 层，我们有 − 1 1 0 0（两个 1 位于一起）
方法
在这种方法中，我们将实现 BFS 或层序遍历以获取同一层的所有节点值，然后我们将找到哪些层包含连续的 1。
我们将使用队列数据结构来实现 BFS 方法，该方法将遵循先进先出的原则。
此外，我们将使用两个嵌套的 while 循环来获取下一层并遍历当前层，在每一层中，我们将维护三个变量来存储 1 的数据。让我们看看代码实现。
示例
#include <bits/stdc++.h>
using namespace std;
// defining class to create structure of the binary tree node
class Tree{
public:
int data; // varialbe to store the data
Tree* left; // pointer to store the left child address
Tree* right; // pointer to store the right child address
// constructor to initialize a new node
Tree(int val){
data = val;
left = nullptr; // making left and right pointer null-pointers
right = nullptr;
}
};
// function to get the number of levels
int countLevels(Tree* root){
queue<Tree*> q; // queue to store the levelwise values of the tree nodes
// defining a base condition
if(root == nullptr){
return 0;
}
// defining required variables
int ans = 0; // varaible to store the number of levels
int k; // variable to store the number of nodes present in the current level
int var1; // first variable indicating the whether any 1 is present in the current level or not
int var2; // second variable indicating whether previous node was 1 or not
int var3; // third variable to indicate any non-consequtive one is present
q.push(root);
// traversing over the queue
while(q.size()){
int k = q.size();// variable to collect current size of queue
var1 = false; // marking all the variables to false
var2 = false;
var3 = false;
while(k--){
Tree* cur = q.front();
q.pop(); // removing first element of queue
if(cur->data == 1){
// if the current node value is 1
if(var1 == false){
// var1 false means no one is trigged yet making both var1 and var2 true to represent 1 is present in level and previous node was also one
var1 = true;
var2 = true;
}
else if(var2 == false){
// if var1 is true then we check this if var2 is false means there is already non-consecutive ones' present
var3 = true;
}
}
else{
// breaking streak of ones by marking var2 as false
var2 = false;
}
// if left child of the current node is not null add it to queue
if(cur->left){
q.push(cur->left);
}
// if right child of the current node is not null add it to the queue
if(cur->right){
q.push(cur->right);
}
}
// if all the ones are present consecutively
if(var1 && !var3){
ans++;
}
}
return ans;// returning the final answer
}
int main(){
// defining the tree
Tree* root = new Tree(0);
root->left = new Tree(0);
root->right = new Tree(1);
root->left->left = new Tree(0);
root->left->right = new Tree(1);
root->right->left = new Tree(1);
root->right->right = new Tree(0);
// calling the function to get the count
cout << "The number of levels which contains consecutive ones are: " << countLevels(root);
return 0;
}
输出
The number of levels which contains consecutive ones are: 2
时间和空间复杂度
上面代码的时间复杂度为 O(N)，其中 N 是给定树中的节点总数，属于线性时间复杂度。
上面代码的空间复杂度为 O(N)，因为我们使用队列的形式额外使用了空间来存储队列中的元素。
结论
在本教程中，我们实现了一个程序来查找给定二叉树的层数，该二叉树的节点值仅包含二进制数字，并且包含 1，且所有 1 都连续存在。我们实现了 bfs 方法来在 O(N) 时间和 O(N) 空间复杂度内找到同一层的所有节点。
更新于： 2023 年 8 月 24 日
浏览量 151 次
广告