C++에서 inorder 방식으로 완전한 이진 트리의 미러 이미지 노드 합계

<시간/>

이 문제에서는 완전한 이진 트리가 제공됩니다. 우리의 임무는 완전한 이진 트리의 미러 이미지 노드의 합을 순서대로 찾는 프로그램을 만드는 것입니다.

여기에서 우리는 왼쪽 태양 나무의 inorder traversal을 찾아야 하고 각 노드에 대해 미러 이미지를 추가해야 합니다. 이것은 우리가 왼쪽 리프 노드를 순회하는 경우 오른쪽 리프 노드의 값을 추가한다는 것을 의미합니다. 미러 이미지 노드이기 때문입니다.

몇 가지 중요한 정의

완전한 이진 트리 마지막 레벨을 제외한 모든 레벨의 노드 수가 가장 많은 이진 트리입니다.

순차 순회 왼쪽 하위 트리를 먼저 방문하고 루트를 방문하고 오른쪽 하위 트리를 방문하는 트리 탐색 기법입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

C++에서 inorder 방식으로 완전한 이진 트리의 미러 이미지 노드 합계

출력 − 9 9 17 2

설명 − 왼쪽 하위 트리의 중위 순회는 5-7-8-1입니다.

모든 노드를 추가하면 이미지가 미러링됩니다.

이 문제를 해결하기 위해 우리는 중위 순회를 사용하여 이진 트리를 순회할 것입니다. 우리는 두 개의 노드를 사용할 것입니다. 하나는 왼쪽 하위 트리를 탐색하고 다른 하나는 노드의 미러를 방문합니다. 예를 들어 왼쪽 하위 트리에 대한 루트 노드가 있고 이 노드에 대해 미러 이미지를 가로지르는 미러루트가 있습니다.

예

솔루션의 작동을 설명하는 프로그램,

#include <iostream>
using namespace std;
typedef struct node {
   int data;
   struct node* left;
   struct node* right;
   node(int d){
      data = d;
      left = NULL;
      right = NULL;
   }
} Node;
void printMirrorSum(Node* root, Node* rootMirror){
   if (root->left == NULL && rootMirror->right == NULL)
      return;
   printMirrorSum(root->left, rootMirror->right);
   cout<<(root->left->data + rootMirror->right->data)<<endl;
   printMirrorSum(root->right, rootMirror->left);
}
int main(){
   Node* root = new Node(1);
   root->left = new Node(7);
   root->right = new Node(2);
   root->left->left = new Node(5);
   root->left->right = new Node(8);
   root->right->left = new Node(9);
   root->right->right = new Node(4);
   cout<<"Sum of node and mirror image nodes are :\n";
   printMirrorSum(root, root);
   if (root)
      cout<<(root->data + root->data);
   return 0;
}

출력

Sum of node and mirror image nodes are :
9
9
17
2