C++ 计算由值为1的节点组成的二叉树的层级数

二叉树是每个节点最多有两个子节点的树。给定一个二叉树，其节点值只有0和1。我们需要找到二叉树中至少有一个1的层级数，并且该层级上的所有1必须连续存在。

示例

让我们通过一个例子来理解：

输入

0
   /    \
  1       0
 / \     / \
1   1   0   0

输出

2

解释

对于第二级和第三级，我们在连续的位置都有所有的“1”。

• 对于第1级，我们有 - 0(没有人存在)

• 对于第2级，我们有 - 1 0(只有1个“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)，因为我们使用额外的空间以队列的形式存储队列中的元素。

结论

在本教程中，我们实现了一个程序来找出给定二叉树的层数，该二叉树只包含二进制数作为节点值，并且它们都是连续的。我们使用广度优先搜索（BFS）的方法，在O(N)的时间复杂度和O(N)的空间复杂度下找到同一级别的所有节点。