数据结构和算法面试题：实现一个函数，将一棵二叉树转换为它的镜像。（递归或者非递归实现）

朱雀 2024-03-16 17:05 15阅读 0赞

## 数据结构和算法面试题：实现一个函数，将一棵二叉树转换为它的镜像。（递归或者非递归实现） ##

简介：实现一个函数，将一棵二叉树转换为它的镜像。（递归或者非递归实现）

该算法的实现思路如下：

1.  对于当前节点，交换其左右子树。
2.  递归地对该节点的左右子树进行镜像转换。

下面是使用C++实现将一棵二叉树转换为它的镜像（非递归实现）的代码，并附带详细注释：

#include <iostream>
    #include <stack>
    
    using namespace std;
    
    // 定义二叉树结构
    struct TreeNode {
        
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x) : val(x), left(nullptr), right(nullptr) {
        }
    };
    
    // 将一棵二叉树转换为它的镜像（非递归实现）
    void mirror_iterative(TreeNode* root) {
        
        if (root == nullptr) return;
    
        stack<TreeNode*> s{
        {
        root}};
        while (!s.empty()) {
        
            TreeNode* node = s.top();
            s.pop();
    
            swap(node->left, node->right); // 交换左右子树
    
            if (node->left != nullptr) s.push(node->left);
            if (node->right != nullptr) s.push(node->right);
        }
    }
    
    int main() {
        
        // 构造一棵二叉树
        TreeNode* root = new TreeNode(4);
        root->left = new TreeNode(2);
        root->right = new TreeNode(7);
        root->left->left = new TreeNode(1);
        root->left->right = new TreeNode(3);
        root->right->left = new TreeNode(6);
        root->right->right = new TreeNode(9);
    
        // 转换并输出镜像结果
        mirror_iterative(root);
    
        cout << root->val << endl;             // 4
        cout << root->left->val << " ";        // 7
        cout << root->left->left->val << " ";  // 9
        cout << root->left->right->val << " "; // 6
        cout << root->right->val << " ";       // 2
        cout << root->right->left->val << " "; // 3
        cout << root->right->right->val << endl;// 1
    
        return 0;
    }

下面是同样功能的递归实现代码，也附有详细注释：

#include <iostream>
    
    using namespace std;
    
    // 定义二叉树结构
    struct TreeNode {
        
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x) : val(x), left(nullptr), right(nullptr) {
        }
    };
    
    // 将一棵二叉树转换为它的镜像（递归实现）
    void mirror_recursive(TreeNode* root) {
        
        if (root == nullptr) return;
    
        swap(root->left, root->right); // 交换当前节点的左右子树
    
        // 递归对左右子树进行镜像操作
        mirror_recursive(root->left);
        mirror_recursive(root->right);
    }
    
    int main() {
        
        // 构造一棵二叉树
        TreeNode* root = new TreeNode(4);
        root->left = new TreeNode(2);
        root->right = new TreeNode(7);
        root->left->left = new TreeNode(1);
        root->left->right = new TreeNode(3);
        root->right->left = new TreeNode(6);
        root->right->right = new TreeNode(9);
    
        // 转换并输出镜像结果
        mirror_recursive(root);
    
        cout << root->val << endl;             // 4
        cout << root->left->val << " ";        // 7
        cout << root->left->left->val << " ";  // 9
        cout << root->left->right->val << " "; // 6
        cout << root->right->val << " ";       // 2
        cout << root->right->left->val << " "; // 3
        cout << root->right->right->val << endl;// 1
    
        return 0;
    }

这两份代码均以定义二叉树结构的方式构建二叉树。`mirror_iterative()`函数使用栈进行非递归实现，从而避免了函数调用的栈深，降低了空间复杂度；而`mirror_recursive()`函数则使用递归实现，代码更加简洁易懂。两个函数的思路都是：对于一个节点，交换其左右子树后，递归地对其左右子树进行同样的操作。