题解 | #二叉树的镜像#

开始看到题目中说有原地算法，想挑战一下的，但是想了一会没什么思路，还是用常规的遍历解法来做了。
逻辑十分简单，遍历头结点，交换左右子树，再依次遍历左右子树，直到遍历所有结点。
使用递归进行遍历，时间复杂度为O(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
        mirror(pRoot);
        return pRoot;
    }
    void mirror(TreeNode* &p){
        if(!p){
            return;
        }
        TreeNode* temp = p->left;
        p->left = p->right;
        p->right = temp;
        mirror(p->left);
        mirror(p->right);
    }
};