C++ 两两交换二叉树中的叶节点

c++server side programmingprogramming

给定一棵二叉树。任务是成对交换叶节点，例如 −

输入 −

输出 −

我们将跟踪指向两个相邻叶节点的两个指针，并在给定的问题中交换它们的值。

寻找解决方案的方法

在这种方法中，我们遍历树，找到叶节点，并跟踪我们的计数器以检查当前计数。主要的技巧是我们的计数器是奇数，所以我们的第一个指针现在指向该节点。当我们的计数器变为偶数时，我们交换数据，因此我们的叶节点被交换。

示例

上述方法的 C++ 代码

#include <bits/stdc++.h>
using namespace std;
struct Node{ // 我们的树节点的结构
    int data;
    struct Node *left, *right;
};
void Swap(Node **a, Node **b){ // 交换实用函数
    Node * temp = *a;
    *a = *b;
    *b = temp;
}
/********用于交换的叶节点指针********/
Node **firstleaf;
Node **secondleaf;
void SwapTheLeafNodes(Node **root, int &count){//递归函数
//交换叶节点
    if (!(*root)) // 如果 root 为空，则返回
        return;
    if(!(*root)->left &&!(*root)->right){ // 叶节点条件
        secondleaf = root; // 现在我们首先让第二个指针指向这个节点
        count++; // 我们也增加计数
        if (count%2 == 0) // 现在如果我们的计数是偶数，这意味着我们有一对，所以我们可以交换它们
            Swap(firstleaf, secondleaf);
        else // 如果计数是奇数，这意味着我们只得到了第一个节点
            firstleaf = secondleaf;
    }
    if ((*root)->left)
          SwapTheLeafNodes(&(*root)->left, count);
    if ((*root)->right)
        SwapTheLeafNodes(&(*root)->right, count);
}
Node* newNode(int data){ // 初始化新节点的函数
    Node *temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
void printInorder(Node* node){ // 中序遍历函数
    if (node == NULL)
       return;
    printInorder(node->left);
    printf("%d ", node->data);
    printInorder(node->right);
}
int main(){
   /* 创建二叉树*/
    节点 *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 << "交换前中序遍历:\n";
    printInorder(root);
    cout << "\n";
    int count = 0; // 用于跟踪叶节点的输出计数器
    SwapTheLeafNodes(&root, count); // 交换节点
    cout << "交换后中序遍历:\n";
    printInorder(root);
    cout << "\n";
    return 0;
}

输出

交换前中序遍历:
4 2 1 6 5 7 3 9 8 10
交换后中序遍历:
6 2 1 4 5 9 3 7 8 10

上述代码的解释

在上述方法中，我们只是构造了两个指针来跟踪我们的叶节点。当我们遇到叶节点时，我们会遍历树。我们首先让第二个指针指向该节点，现在我们增加一个计数变量，如果计数是偶数，那么我们交换节点；如果计数是奇数，那么这意味着我们只找到了配对的第一个元素，所以我们将该值存储在第一个指针中，这就是我们的函数的工作原理。