資料結構
網路
關係型資料庫管理系統
作業系統
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 次
廣告