C++で二分木の完全性を確認する

二分木があるとします。ツリーが完全な二分木であるかどうかを確認する必要があります。レベルnの完全な二分木はn-1の完全なレベルを持ち、レベルnのすべてのノードは左から埋められます。したがって、入力ツリーが次のような場合-

これは完全な二分木であるため、出力はtrueになります。

これを解決するには、次の手順に従います-

• ツリーが空の場合は、nullを返します

• キューqを作成し、それにルートを挿入します

• フラグを設定：=true

• qにはいくつかの要素があります

  • sz：=キューのサイズ

  • szは0ではありません

    • node：=キューから削除した後のノード

    • ノードがサブツリーを離れた場合、

      • フラグが設定されている場合は、ノードの左側のサブツリーをqに挿入し、それ以外の場合はfalseを返します

    • それ以外の場合はフラグ：=false

    • ノードに正しいサブツリーがある場合、

      • フラグが設定されている場合は、ノードの右側のサブツリーをqに挿入します。それ以外の場合は、falseを返します

    • フラグ：=false

    • sz：=sz – 1

• リターンチュール

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = NULL;
      right = NULL;
   }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
      }else{
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
            temp->right = new TreeNode(val);
         else
            temp->right = new TreeNode(0);
         return;
      }else{
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int> v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
class Solution {
   public:
   bool isCompleteTree(TreeNode* root) {
      if(!root)return true;
      queue <TreeNode*> q;
      q.push(root);
      bool isComplete = true;
      while(!q.empty()){
         int sz = q.size();
         while(sz--){
            TreeNode* node = q.front();
            q.pop();
            if(node->left){
               if(isComplete){
                  q.push(node->left);
               }else return false;
            }else{
               isComplete = false;
            }
            if(node->right){
               if(isComplete){
                  q.push(node->right);
               }else return false;
            }else{
               isComplete = false;
            }
         }  
      }
      return true;
   }
};
main(){
   vector<int> v = {1,2,3,4,5,6};
   TreeNode *r1 = make_tree(v);
   Solution ob;
   cout << (ob.isCompleteTree(r1));
}

入力

{1,2,3,4,5,6}

出力

1