주어진 이진 트리. 작업은 리프 노드를 쌍으로 바꾸는 것입니다. 예를 들어 -
입력 -
출력 -
우리는 두 개의 인접한 리프 노드를 가리키는 두 개의 포인터를 추적하고 주어진 문제에서 값을 교환합니다.
해결책을 찾기 위한 접근 방식
이 접근 방식에서는 트리를 탐색하고 리프 노드를 찾고 카운터를 추적하여 현재 카운트를 확인합니다. 주요 트릭은 카운터가 홀수이므로 첫 번째 포인터가 이제 해당 노드를 가리킵니다. 카운터가 짝수일 때 데이터를 교환하므로 리프 노드가 교환됩니다.
예시
위 접근 방식에 대한 C++ 코드
#include <bits/stdc++.h>
using namespace std;
struct Node{ // structure of our tree node
int data;
struct Node *left, *right;
};
void Swap(Node **a, Node **b){ // the swapping utility function
Node * temp = *a;
*a = *b;
*b = temp;
}
/********Pointers for leaf nodes for swapping********/
Node **firstleaf;
Node **secondleaf;
void SwapTheLeafNodes(Node **root, int &count){//recursive function for
//Swapping leaf nodes
if (!(*root)) // if root is null we return
return;
if(!(*root)->left &&!(*root)->right){ // condition for leaf node
secondleaf = root; // now we firstly make our second pointer point to this node
count++; // we also increment the count
if (count%2 == 0) // now if our count is even that means we have a pair so we can swap them
Swap(firstleaf, secondleaf);
else // if count is odd so that means we only got first node yet
firstleaf = secondleaf;
}
if ((*root)->left)
SwapTheLeafNodes(&(*root)->left, count);
if ((*root)->right)
SwapTheLeafNodes(&(*root)->right, count);
}
Node* newNode(int data){ // function for initializing new node
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void printInorder(Node* node){ // inorder traversal function
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
int main(){
/* Creating binary tree*/
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->right->left = newNode(5);
root->right->right = newNode(8);
root->right->left->left = newNode(6);
root->right->left->right = newNode(7);
root->right->right->left = newNode(9);
root->right->right->right = newNode(10);
cout << "Inorder traversal before swap:\n";
printInorder(root);
cout << "\n";
int count = 0; // out counter for keeping track of leaf nodes
SwapTheLeafNodes(&root, count); // swapping the nodes
cout << "Inorder traversal after swap:\n";
printInorder(root);
cout << "\n";
return 0;
} 출력
Inorder traversal before swap: 4 2 1 6 5 7 3 9 8 10 Inorder traversal after swap: 6 2 1 4 5 9 3 7 8 10
위 코드 설명
위의 접근 방식에서 우리는 단순히 리프 노드를 추적할 두 개의 포인터를 만들고 있습니다. 리프 노드를 만나면 트리를 탐색합니다. 먼저 두 번째 포인터가 해당 노드를 가리키도록 합니다. 이제 개수가 짝수이면 개수 변수를 증가시키므로 노드를 교체하고 개수가 홀수이면 쌍의 첫 번째 요소만 찾았습니다. 그 값을 첫 번째 포인터에 저장하고 이것이 우리의 함수가 작동하는 방식입니다.
결론
이 자습서에서는 이진 트리에서 Pairwise Swap 리프 노드 문제를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하는 완전한 접근 방식( Normal 및 Efficient)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 튜토리얼이 도움이 되기를 바랍니다.