C++에서 이진 트리의 최대 너비

문제 설명

주어진 이진 트리에서 주어진 트리의 최대 너비를 구하는 함수를 작성하십시오. 트리의 너비는 모든 레벨의 너비의 최대값입니다.

아래 트리 고려 -

      10
     / \
    7   4
   / \   \
  9   2   1
         / \
        2   5
1. Width at level 1: 1
2. Width at level 2: 2
3. Width at level 3: 3
4. Width at level 4: 2
For above tree answer is 3.

알고리즘

1. Use level order traversal to find the answer

예시

#include <bits/stdc++.h>
using namespace std;
struct node {
   public:
      int data;
      node* left;
      node* right;
};
int getWidth(node* root, int level);
int height(node* node);
node* newNode(int data);
int getMaxWidth(node* root){
   int maxWidth = 0;
   int width;
   int h = height(root);
   int i;
   for (i = 1; i <= h; ++i) {
      width = getWidth(root, i);
      if (width > maxWidth) {
         maxWidth = width;
      }
   }
   return maxWidth;
}
int getWidth(node* root, int level){
   if (root == NULL) {
      return 0;
   }
   if (level == 1) {
      return 1;
   }
   else if (level > 1) {
      return getWidth(root->left, level - 1) + getWidth(root->right, level - 1);
   }
}
int height(node* node){
   if (node == NULL) {
      return 0;
   }
   int lHeight = height(node->left);
   int rHeight = height(node->right);
   return (lHeight > rHeight)? (lHeight + 1): (rHeight + 1);
}
node* newNode(int data){
   node* Node = new node();
   Node->data = data;
   Node->left = NULL;
   Node->right = NULL;
   return(Node);
}
int main(){
   node *root = newNode(10);
   root->left = newNode(7);
   root->right = newNode(4);
   root->left->left = newNode(9);
   root->left->right = newNode(2);
   root->right->right = newNode(1);
   root->right->right->left = newNode(2);
   root->right->right->right = newNode(5);
   cout<<"Maximum width = " << getMaxWidth(root) << endl;
   return 0;
}

출력

위 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -

Maximum width = 3