剑指 Offer 27. 二叉树的镜像

难度简单
请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

 4<br />   /   \<br />  2     7<br /> / \   / \<br />1   3 6   9<br />镜像输出：
 4<br />   /   \<br />  7     2<br /> / \   / \<br />9   6 3   1<br />示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

方法一：递归法

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var mirrorTree = function(root) {
    if(root==null) return null;
    const node = root.left;
    root.left = mirrorTree(root.right)
    root.right = mirrorTree(node)
    return root
};

复杂度分析：
时间复杂度 O(N)O(N) ： 其中 NN 为二叉树的节点数量，建立二叉树镜像需要遍历树的所有节点，占用 O(N)O(N) 时间。
空间复杂度 O(N)O(N) ： 最差情况下（当二叉树退化为链表），递归时系统需使用 O(N)O(N) 大小的栈空间。

方法二：辅助栈（或者队列)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var mirrorTree = function(root) {
    if(root==null) return null;
    let stack = [root]
    while(stack.length!=0){
        let node = stack.pop()
        if(node.left!=null) stack.push(node.left);
        if(node.right!=null) stack.push(node.right);
        let tmp = node.left
        node.left = node.right
        node.right = tmp
    }
    return root
};

复杂度分析：
时间复杂度 O(N)O(N) ： 其中 NN 为二叉树的节点数量，建立二叉树镜像需要遍历树的所有节点，占用 O(N)O(N) 时间。
空间复杂度 O(N)O(N) ： 如下图所示，最差情况下，栈 stack 最多同时存储N+1/2个节点，占用 O(N) 额外空间。

参考：
作者：jyd
链接：https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/solution/mian-shi-ti-27-er-cha-shu-de-jing-xiang-di-gui-fu-/
来源：力扣（LeetCode）