描述

操作给定的二叉树，将其变换为源二叉树的镜像。

解题思路

因为是从原二叉树得到镜像二叉树，镜像我们知道是对称的，则我们需要把二叉树的左右子树进行交换

递归 时间复杂度O(n)。空间复杂度O(logn)

    public TreeNode Mirror (TreeNode pRoot) {
        if (pRoot == null){
            return null;
        }
        getMirrorTree(pRoot);
        return pRoot;
        // write code here
    }
    public void getMirrorTree(TreeNode root){
        if (root == null){
            return;
        }
        // 交换左右子树
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        // 继续交换左子树
        Mirror(root.left);
        // 继续交换右子树
        Mirror(root.right);
    }

递归法图解

树初始状态

一次递归后，左右子树互换位置，即6子树与10子树互换位置

递归左子树10

左子树子树都为null,递归右子树

递归结束

非递归 时间复杂度O(n),空间复杂度O(n)

将递归算法转为非递归算法，我们可以借助队列实现先进先出

    public static TreeNode Mirror (TreeNode pRoot) {
        if (pRoot == null){
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        // 插入root节点
        queue.add(pRoot);
        // 当队列中节点数目为空表述交换完成
        while(queue.size() != 0){
            // 弹出一个节点
            TreeNode node = queue.poll();
            // 左右子树交换
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
            // 如果左子树不为空
            if (node.left != null) {
                queue.add(node.left);
            }
            // 如果右子树不为空
            if (node.right != null){
                queue.add(node.right);
            }
        }
        return pRoot;
        // write code here
    }

递归法图解