C++で二分木が完全二分木かどうかを判定する方法

完全二分木とは？

二分木が与えられたとき、その木が完全二分木（Complete Binary Tree）であるかどうかを判定する問題を考えてみましょう。完全二分木とは、深さ n の木において、上から n-1 レベルまですべてのノードが埋まっており、最下層のノードは必ず左側から順に配置されている二分木のことです。

例えば、次のような入力木が与えられたとします。

この場合、すべてのノードが左詰めで配置されているため、出力は true（完全二分木である）になります。

解法のアプローチ

この問題は、幅優先探索（BFS）とフラグ変数を組み合わせることで効率的に解くことができます。具体的な手順は以下の通りです。

• 木が空の場合は true を返す

• キュー q を作成し、ルートノードを挿入する

• フラグを true に設定する

• キューに要素が存在する間、以下を繰り返す

  • sz := キューの現在のサイズを取得

  • sz が 0 でない限り、以下を繰り返す

    • node := キューから先頭のノードを取り出す

    • node に左の子が存在する場合 → フラグが立っていればキューに挿入し、そうでなければ false を返す

    • 左の子が存在しない場合 → flag := false に設定

    • node に右の子が存在する場合 → フラグがまだ立っていればキューに挿入し、そうでなければ false を返す

    • 右の子が存在しない場合 → flag := false に設定

    • sz := sz - 1

• すべてのノードを処理し終えたら true を返す

このアルゴリズムのポイントは、一度でも「子を持たないノード」を見つけたらフラグを倒し、それ以降に子を持つノードが出現した時点で完全二分木ではないと即座に判断できる点です。これにより、無駄な探索を省きながら正確な判定が可能になります。

C++での実装例

理解を深めるために、以下の実装例をご覧ください。

サンプルコード

#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

出力が 1（true）となっており、この木が完全二分木であることが正しく判定されました。計算量は各ノードを一度だけ訪問するため O(n)、空間計算量もキューのサイズに依存して O(n) となります。