题解 | #二叉树的镜像#

思路：

题目的主要信息：

将二叉树镜像，即将其所有左右子树交换

我们可以考虑自底向上依次交换二叉树的左右结点。

方法一：递归
具体做法：
采用递归的方法，首先深入到二叉树的叶子结点，交换其左右，然后依次往上交换。

class Solution {
public:
    TreeNode* Mirror(TreeNode* pRoot) {
        if (pRoot == NULL) //空树返回
            return NULL;
        TreeNode* left = Mirror(pRoot->left);  //先递归子树
        TreeNode* right = Mirror(pRoot->right);
        pRoot->left = right; //交换
        pRoot->right = left;
        return pRoot;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，访问二叉树所有结点各一次
空间复杂度： $O(n)$ ，递归栈最大值

方法二：栈
具体做法：
能够用递归的，我们也可以用栈来实现。栈的访问是一种自顶向下的访问，因此我们需要在左右子结点入栈后直接交换，然后再访问后续栈中内容。
图片说明

class Solution {
public:
    TreeNode* Mirror(TreeNode* pRoot) {
        if(pRoot == NULL)  //空树
            return NULL;
        stack<TreeNode*> s; //辅助栈
        s.push(pRoot);
        while (!s.empty())
        {
            TreeNode* node = s.top();
            s.pop();
            if (node->left != NULL) s.push(node->left);
            if (node->right != NULL) s.push(node->right); //左右结点入栈
            TreeNode* temp = node->left;  //交换左右
            node->left = node->right;
            node->right = temp;
        }
        return pRoot;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，每个结点遍历一次
空间复杂度： $O(n)$ ，最坏情况下，栈的大小