二分木のC++ペアワイズスワップリーフノード

二分木が与えられます。タスクは、リーフノードをペアワイズスワップすることです。たとえば、-

入力-

出力-

隣接する2つのリーフノードを指す2つのポインターを追跡し、特定の問題でそれらの値を交換します。

解決策を見つけるためのアプローチ

このアプローチでは、ツリーをトラバースし、リーフノードを見つけ、カウンターを追跡して現在のカウントを確認します。主なトリックは、カウンターが奇数であるため、最初のポインターがそのノードを指していることです。カウンターが均等になると、データが交換されるため、リーフノードが交換されます。

例

上記のアプローチの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

上記のコードの説明

上記のアプローチでは、リーフノードを追跡する2つのポインタを作成しているだけです。リーフノードに遭遇すると、ツリーをトラバースします。最初に2番目のポインタをそのノードにポイントします。カウントが偶数の場合はカウント変数をインクリメントします。ノードを交換し、カウントが奇数の場合は、ペアの最初の要素のみが見つかったことを意味します。その値を最初のポインタに格納します。これが関数の動作です。

結論

このチュートリアルでは、バイナリツリーのペアワイズスワップリーフノードの問題を解決します。また、この問題のC ++プログラムと、この問題を解決するための完全なアプローチ（通常および効率的）についても学びました。同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。このチュートリアルがお役に立てば幸いです。