이 문제에서는 이진 트리가 주어지고 이진 트리의 모든 리프 노드를 오른쪽에서 왼쪽으로 인쇄해야 합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력 -
출력 − 7 4 1
이 문제를 해결하려면 이진 트리를 탐색해야 합니다. 이 순회는 두 가지 방법으로 수행할 수 있습니다. -
선주문 순회 - 이 순회는 재귀를 사용합니다. 여기에서 루트, 왼쪽, 오른쪽 하위 트리를 순회합니다. 리프 노드를 만나면 인쇄하고, 그렇지 않으면 노드의 자식을 확인하고 탐색하여 리프 노드를 찾습니다.
예시
솔루션 구현을 보여주는 프로그램 −
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
Node* insertNode(int data) {
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void findLeafNode(Node* root) {
if (!root)
return;
if (!root->left && !root->right) {
cout<<root->data<<"\t";
return;
}
if (root->right)
findLeafNode(root->right);
if (root->left)
findLeafNode(root->left);
}
int main() {
Node* root = insertNode(21);
root->left = insertNode(5);
root->right = insertNode(11);
root->left->left = insertNode(8);
root->left->right = insertNode(98);
root->right->left = insertNode(2);
root->right->right = insertNode(8);
cout<<"Leaf nodes of the tree from right to left are:\n";
findLeafNode(root);
return 0;
} 출력
Leaf nodes of the tree from right to left are − 18 2 98 8
우편 주문 순회 - 리프 노드를 찾기 위한 이 순회는 반복을 사용합니다. 스택을 사용하여 데이터를 저장하고 후위 방식으로 트리를 탐색하고(첫 번째 오른쪽 하위 트리, 왼쪽 하위 트리, 그 다음 루트) 리프 노드를 인쇄합니다.
예시
솔루션 구현을 보여주는 프로그램 −
#include<bits/stdc++.h>
using namespace std;
struct Node {
Node* left;
Node* right;
int data;
};
Node* insertNode(int key) {
Node* node = new Node();
node->left = node->right = NULL;
node->data = key;
return node;
}
void findLeafNode(Node* tree) {
stack<Node*> treeStack;
while (1) {
if (tree) {
treeStack.push(tree);
tree = tree->right;
} else {
if (treeStack.empty())
break;
else {
if (treeStack.top()->left == NULL) {
tree = treeStack.top();
treeStack.pop();
if (tree->right == NULL)
cout<<tree->data<<"\t";
}
while (tree == treeStack.top()->left) {
tree = treeStack.top();
treeStack.pop();
if (treeStack.empty())
break;
}
if (!treeStack.empty())
tree = treeStack.top()->left;
else
tree = NULL;
}
}
}
}
int main(){
Node* root = insertNode(21);
root->left = insertNode(5);
root->right = insertNode(11);
root->left->left = insertNode(8);
root->left->right = insertNode(98);
root->right->left = insertNode(2);
root->right->right = insertNode(18);
cout<<"Leaf nodes of the tree from right to left are:\n";
findLeafNode(root);
return 0;
} 출력
Leaf nodes of the tree from right to left are − 18 2 98 8