C++의 리프 노드에서 거리 k에 있는 모든 노드를 인쇄합니다.

이 문제에서는 이진 트리와 숫자 K가 제공됩니다. 리프 노드에서 k 거리에 있는 트리의 모든 노드를 인쇄해야 합니다.

이진 트리 각 노드가 최대 2개의 노드(1/2/없음)를 갖는 특수 트리입니다.

리프 노드 바이너리 트리의 는 트리 끝에 있는 노드입니다.

이 문제에서 리프 노드로부터의 거리는 리프 노드보다 높은 수준에 있는 노드입니다. 레벨 4의 리프 노드에서 거리 2의 노드가 레벨 2에 있다고 가정합니다.

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

K =2

출력 − 6 9.

이 문제를 해결하기 위해 트리를 탐색합니다. 모든 상위 노드 집합(상위 노드라고도 함)은 리프 노드에 도달하는 수준별로 저장합니다. 이제 리프 노드에서 k 거리에 있는 조상을 인쇄합니다. 방문한 노드의 순회 표시는 중복을 피하기 위해 중요하며 이 목적을 위해 부울 배열을 사용합니다 -

코드는 트리 순회만 사용하므로 복잡성은 n에 비례합니다. 시간 복잡도:O(n)

예시

우리의 논리를 설명하는 프로그램 -

#include <iostream>
using namespace std;
#define MAX_HEIGHT 10000
struct Node {
   int key;
   Node *left, *right;
};
Node* insertNode(int key){
   Node* node = new Node;
   node->key = key;
   node->left = node->right = NULL;
   return (node);
}
void nodesKatDistance(Node* node, int path[], bool visited[], int pathLen, int k){
   if (node==NULL) return;
   path[pathLen] = node->key;
   visited[pathLen] = false;
   pathLen++;
   if (node->left == NULL && node->right == NULL && pathLen-k-1 >= 0 && visited[pathLen-k-1] == false){
      cout<<path[pathLen-k-1]<<"\t";
      visited[pathLen-k-1] = true;
      return;
   }
   nodesKatDistance(node->left, path, visited, pathLen, k);
   nodesKatDistance(node->right, path, visited, pathLen, k);
}
void printNodes(Node* node, int k){
   int path[MAX_HEIGHT];
   bool visited[MAX_HEIGHT] = {false};
   nodesKatDistance(node, path, visited, 0, k);
}
int main(){
   Node * root = insertNode(6);
   root->left = insertNode(3);
   root->right = insertNode(9);
   root->left->right = insertNode(4);
   root->right->left = insertNode(8);
   root->right->right = insertNode(10);
   root->right->left->left = insertNode(5);
   root->right->left->right = insertNode(1);
   int k = 2 cout<<"All nodes at distance "<<k<<" from leaf node are:\n";
   printNodes(root, k);
   return 0;
}

출력

리프 노드에서 거리 2에 있는 모든 노드는 -

6 9