C++에서 중위 순회(inorder traversal)의 n번째 노드 찾기

이 문제에서 우리는 이진 트리와 정수 N이 주어집니다. 작업은 이진 트리의 inorder traversal에서 n번째 노드를 찾는 것입니다.

바이너리 트리에는 각 노드가 최대 2개의 자식을 가질 수 있다는 특수한 조건이 있습니다.

순회는 트리의 모든 노드를 방문하는 프로세스이며 해당 값도 출력할 수 있습니다.

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

입력

N = 6

출력

3

설명

inorder traversal of tree : 4, 2, 5, 1, 6, 3, 7

솔루션 접근 방식

아이디어는 재귀 호출을 사용하여 수행되는 이진 트리의 순회를 사용하는 것입니다. 각 호출에서 먼저 왼쪽 하위 트리에 대해 preOrder()를 호출하고 루트 노드를 탐색한 다음 preOrder()를 호출합니다. 이 순회 동안 우리는 노드의 수를 세고 카운트가 N인 노드를 인쇄합니다.

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

예시

#include <iostream>
using namespace std;
struct Node {
   int data;
   Node *left, *right;
};
struct Node* createNode(int item){
   Node* temp = new Node;
   temp->data = item;
   temp->left = NULL;
   temp->right = NULL;
   return temp;
}
void findInOrderTraversalRec(struct Node* node, int N){
   static int count = 0;
   if (node == NULL)
      return;
   if (count <= N) {
      findInOrderTraversalRec(node->left, N);
      count++;
      if (count == N)
         cout<<node->data;
      findInOrderTraversalRec(node->right, N);
   }
}
int main() {
   struct Node* root = createNode(1);
   root->left = createNode(2);
   root->right = createNode(3);
   root->left->left = createNode(4);
   root->left->right = createNode(5);
   root->right->left = createNode(6);
   root->right->right = createNode(7);
   int N = 6;
   cout<<N<<"th node in inorder traversal is ";
   findInOrderTraversalRec(root, N);
   return 0;
}

출력

6th node in inorder traversal is 3