이 문제에서는 이진 트리, 대상 노드 및 정수 K가 제공됩니다. 대상 노드에서 거리 K에 있는 트리의 모든 노드를 인쇄해야 합니다. .
이진 트리 각 노드가 최대 2개의 노드(1/2/없음)를 갖는 특수 트리입니다.
문제를 이해하기 위해 예를 들어보겠습니다.
K =2
대상 노드:9
출력 -
5 1 3.
설명 -
거리는 더 높거나 낮거나 같은 노드에 대해 취할 수 있습니다. 따라서 그에 따라 노드를 반환합니다.
이 문제를 해결하려면 대상 노드에서 K 거리에 있는 노드 유형이 무엇인지 이해해야 합니다.
위의 시험에서 우리는 k 개의 먼 노드가 대상 노드의 하위 트리(5 및 1)에 있거나 대상 노드의 조상 하위 트리(3)의 아무 곳에나 있을 수 있음을 알 수 있습니다.
이제 첫 번째 경우의 솔루션을 찾는 방법은 대상 노드의 하위 트리를 탐색하고 대상에서 노드의 거리가 K인지 확인하는 것입니다. 그렇다면 노드를 인쇄하십시오.
두 번째 경우에는 대상에 대한 조상 노드와 이러한 조상의 하위 트리를 확인하고 대상에서 거리 K에 있는 모든 항목을 인쇄해야 합니다.
아래 프로그램은 우리 솔루션의 구현을 보여줍니다 -
예시
#include <iostream>
using namespace std;
struct node {
int data;
struct node *left, *right;
};
void printSubtreeNodes(node *root, int k) {
if (root == NULL || k < 0) return;
if (k==0){
cout<<root->data<<"\t";
return;
}
printSubtreeNodes(root->left, k-1);
printSubtreeNodes(root->right, k-1);
}
int printKNodes(node* root, node* target , int k){
if (root == NULL) return -1;
if (root == target){
printSubtreeNodes(root, k);
return 0;
}
int dl = printKNodes(root->left, target, k);
if (dl != -1){
if (dl + 1 == k)
cout<<root->data<<"\t";
else
printSubtreeNodes(root->right, k-dl-2);
return 1 + dl;
}
int dr = printKNodes(root->right, target, k);
if (dr != -1){
if (dr + 1 == k)
cout << root->data << endl;
else
printSubtreeNodes(root->left, k-dr-2);
return 1 + dr;
}
return -1;
}
node *insertNode(int data){
node *temp = new node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
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->right->left = insertNode(5);
root->right->right->right = insertNode(1);
node * target = root->right;
int K = 2;
cout<<"Nodes at distance "<<K<<" from the target node are :\n";
printKNodes(root, target, K);
return 0;
} 출력
Nodes at distance 2 from the target n tode are − 5 1 3