C++에서 완전한 트리 노드 계산

완전한 이진 트리가 있다고 가정하고 노드 수를 계산해야 합니다. 트리가 다음과 같다면 -

따라서 출력은 6이 됩니다.

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

• 재귀적 접근 방식을 사용합니다. 이 메서드인 countNodes()는 루트를 인수로 사용합니다.
• hr :=0 및 hl :=0
• 루트로 두 개의 노드 l 및 r 생성
• l이 비어 있지 않은 동안
  • hl 1 증가
  • l :=l의 왼쪽
• r이 비어 있지 않은 동안
  • r :=r의 오른쪽
  • 시간을 1 증가
• hl =hr이면 (2 ^ hl) – 1을 반환합니다.
• return 1 + countNodes(루트의 왼쪽) + countNodes(루트의 오른쪽)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
      int val;
      TreeNode *left, *right;
      TreeNode(int data){
         val = data;
         left = 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:
   int fastPow(int base, int power){
      int res = 1;
      while(power > 0){
         if(power & 1) res *= base;
         base *= base;
         power >>= 1;
      }
      return res;
   }
   int countNodes(TreeNode* root) {
      int hr = 0;
      int hl = 0;
      TreeNode* l = root;
      TreeNode* r = root;
      while(l){
         hl++;
         l = l->left;
      }
      while(r){
         r = r->right;
         hr++;
      }
      if(hl == hr) return fastPow(2, hl) - 1;
      return 1 + countNodes(root->left) + countNodes(root->right);
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3,4,5,6,7,8,9,10};
   TreeNode *node = make_tree(v);
   cout << (ob.countNodes(node));
}

입력

[1,2,3,4,5,6,7,8,9,10]

출력

10