题解 | #二叉树的镜像#

题意思路：
操作给定的二叉树，将其变换为源二叉树的镜像。
也就是将二叉树的每个节点的左子树换成右子树，右子树换成左子树

方法一:递归处理
先处理当前root的左右节点，使当前节点的左子树与右子树交换，达到镜像目的，

然后再递归处理左子树和右子树即可。

特例当pRoot为空时，直接返回pRoot。
复杂度分析

时间复杂度：O(N)，N为树的节点数目，遍历数组；

空间复杂度：O(N)，数组存储与读取数据。

图解：

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 *    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    TreeNode* Mirror(TreeNode* pRoot) {
        // write code here
        if(pRoot==NULL)return pRoot;//特判若节点为空则返回
        TreeNode *temp=pRoot->left;//定义一个新节点等于根节点的左子树
        pRoot->left=pRoot->right;//将左子树赋值为右子树
        pRoot->right=temp;//右子树赋值为存储了左子树的新节点
        Mirror(pRoot->left);//递归镜像左子树
        Mirror(pRoot->right);//递归镜像右子树
        return pRoot;

    }
};

方法二:栈

利用栈的性质先进后出的特性

可以让左子树先进 然后右子树后进，利用先进后出的方式使右子树与左子树进行交换

特例当pRoot为空时，直接返回pRoot

复杂度分析

时间复杂度：O(N)，N为树的节点数目，遍历数组；

空间复杂度：O(N)，数组存储与读取数据。

代码：

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 *    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    TreeNode* Mirror(TreeNode* pRoot) {
        // write code here
        if(pRoot==NULL)return pRoot;//特判若节点为空则返回
        stack<TreeNode*>st;//利用栈的先进后出的性质
        st.push(pRoot);//将根节点加入栈
        while(st.size()){
            TreeNode* node =st.top();//新建节点存储栈中节点
            st.pop();
            if(node->left!=NULL){//若当前节点左子树不为空则加入栈中
                st.push(node->left);
            }
            if(node->right!=NULL){//若当前节点右子树不为空则加入栈中
                st.push(node->right);
            }
            TreeNode *tmp=node->left;//交换左右子树
            node->left=node->right;
            node->right=tmp;
        }
        return pRoot;
    }
};