[数据结构与算法]牛客BM33 二叉树的镜像

链接：https://www.nowcoder.com/practice/a9d0ecbacef9410ca97463e4a5c83be7?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj

题目描述
操作给定的二叉树，将其变换为源二叉树的镜像。
数据范围：二叉树的节点数 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}

解法：
官方解法一：后序遍历，再交换
官方解法二：利用栈，先入后出 的特性进行交换

上述两种方法都不是那么直观
我的方法：
利用 前序（根左右）和 双指针
既然是要 左右 交换，很自然地就想到了 前序（根左右），根 是不动的。 利用递归的思想，每次都把 根节点的左右子树进行交换，依次进行
图解：

这里给出 JavaScript 和 C语言 的代码，C++ JAVA是类似的，换个写法而已

function Mirror( pRoot ) {
    // write code here
    if(pRoot === null) return null
    // left right 分别指向当前根节点的左右子树
    let left=pRoot.left,right = pRoot.right
    // 交换当前根节点左右子树的指向
    pRoot.left = right
    pRoot.right = left
    // 递归 对左右子树进行交换，此时放 pRoot.left 还是 left 都行
    // 因为每一次递归，都相当于是一颗新的二叉树
    Mirror(pRoot.left)
    Mirror(pRoot.right)
    return pRoot
}

C语言

struct TreeNode* Mirror(struct TreeNode* pRoot ) {
    // write code here
    if(pRoot == NULL) return NULL;
    struct TreeNode * pleft=  pRoot -> left;
    struct TreeNode * pright = pRoot -> right;
    pRoot -> left = pright;
    pRoot -> right = pleft;
    Mirror(pRoot -> left);
    Mirror(pRoot -> right);
    return pRoot;
}

思路很清晰，对吧！点个赞吧~~~