剑指offer——JZ27 二叉树的镜像 解题思路与具体代码【C++】

一、题目描述与要求

二叉树的镜像_牛客题霸_牛客网 (nowcoder.com)

题目描述

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

数据范围：二叉树的节点数 0≤n≤1000 ， 二叉树每个节点的值 0≤val≤1000

要求： 空间复杂度 O(n) 。本题也有原地操作，即空间复杂度 O(1) 的解法，时间复杂度 O(n)

比如：

源二叉树

示例

示例1：

输入：{8,6,10,5,7,9,11}

返回值：{8,10,6,11,9,7,5}

说明：如题面所示

示例2：

输入：{}

返回值：{}

---

二、解题思路

首先判断二叉树是否为空树，是的话直接返回空；

然后就是分别递归遍历左子树与右子树直至叶子结点，然后将左右结点进行交换，逐层递归回根结点，最后返回根结点pRoot。

---

三、具体代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    TreeNode* Mirror(TreeNode* pRoot) {
        //空树
        if(pRoot==nullptr) return nullptr;
        //递归子树
        TreeNode* left=Mirror(pRoot->left);
        TreeNode* right=Mirror(pRoot->right);
        //交换
        pRoot->left=right;
        pRoot->right=left;
        return pRoot;
    }
};