题解 | #二叉树的镜像#

NC72 二叉树的镜像

题意

操作给定的二叉树，将其变换为源二叉树的镜像。

1. 魔改交换变量（前序遍历1）

我们在大一的C语言课上学过，交换两个变量a和b的代码是：

int c = a;
a = b;
b = c;

这道题跟交换两个变量差不多，稍微魔改一下上面的交换过程，把左孩子赋值为右子树的镜像，右孩子赋值为左子树的镜像，就可以了。

注意这里不是赋值为右子树，而是右子树的镜像。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */

    using PNode = TreeNode*;
    TreeNode* Mirror(TreeNode* pRoot) {
        if (!pRoot) return nullptr; // 空树

        // 魔改的交换两个变量
        PNode temp = pRoot->left;
        pRoot->left = Mirror(pRoot->right);
        pRoot->right = Mirror(temp);

        return pRoot;
    }
};

时间复杂度: $O(n)$ . 每个点遍历了一次
空间复杂度: $O(n)$ . 每个点递归了一次，每层的空间复杂度为 $O(1)$

2. 层序遍历bfs

本题要求的是输出二叉树的镜像，就是每一个节点的左右子节点进行交换，再交换孩子的左右节点。

那么按“辈分”遍历，首先想到的思路就是bfs，本题可以用bfs解决。随便画一个二叉树看下：
图片说明

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    using PNode = TreeNode*;
    TreeNode* Mirror(TreeNode* pRoot) {
        if (!pRoot) return nullptr; // 特判空树，考虑边界情况

        queue<PNode> q;
        q.push(pRoot);

        while (!q.empty()) {
            PNode p = q.front();
            q.pop();

            // 交换当前节点的左右子节点
            swap(p->left, p->right);

            // 继续遍历下一层
            if (p->left) q.push(p->left);
            if (p->right) q.push(p->right);
        }

        return pRoot;
    }
};

时间复杂度: O(n). 每个点遍历了一次
空间复杂度: O(n). 定义了大小为n的队列。

3. 前序遍历2/中序/后序遍历法

方法一相当于前序遍历，方法二相当于层次遍历，实际上中序/后序遍历也可以解决这道题。anyway，遍历到的每个点都将其左右互换就可以了。

class Solution {
public:
    // 后序遍历法
    using PNode = TreeNode*;
    TreeNode* Mirror(TreeNode* pRoot) {
        if (!pRoot) return nullptr;

        Mirror(pRoot->left);
        Mirror(pRoot->right);
        swap(pRoot->left, pRoot->right); // 把这句话放到第8行上面，也可以作为另一种前序遍历的解法

        return pRoot;
    }
};

class Solution {
public:
    // 中序遍历法
    using PNode = TreeNode*;
    TreeNode* Mirror(TreeNode* pRoot) {
        if (!pRoot) return nullptr;

        Mirror(pRoot->left);
        swap(pRoot->left, pRoot->right);
        Mirror(pRoot->left); // 需要注意，left和right互换了，所以递归右子树要写left。

        return pRoot;
    }
};

时间、空间复杂度同方法一。

4. 总结

本题方法较多，也较为简单，用各种遍历法均能解决，是复习二叉树各种遍历方式的一道很基础的好题。