C++에서 이진 트리의 완성도 확인

<시간/>

이진 트리가 있다고 가정합니다. 트리가 완전한 이진 트리인지 여부를 확인해야 합니다. 레벨 n의 완전한 이진 트리는 n-1개의 완전한 레벨을 가지며 레벨 n의 모든 노드는 왼쪽부터 채워집니다. 따라서 입력 트리가 다음과 같은 경우 -

C++에서 이진 트리의 완성도 확인

그러면 완전한 바이너리 트리이므로 출력은 true가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

트리가 비어 있으면 null을 반환합니다.
큐 q를 만들고 거기에 루트를 삽입하십시오.
플래그 설정 :=true
q에는 몇 가지 요소가 있습니다.
- sz :=큐의 크기
- sz가 0이 아닌 동안
  - node :=대기열에서 삭제한 후의 노드
  - 노드가 하위 트리를 떠난 경우
    - 플래그가 설정되면 노드의 왼쪽 하위 트리를 q에 삽입하고 그렇지 않으면 false를 반환합니다.
  - 그렇지 않으면 플래그 :=false
  - 노드에 올바른 하위 트리가 있으면
    - 플래그가 설정되면 노드의 오른쪽 하위 트리를 q에 삽입하고 그렇지 않으면 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}