27-二叉树的镜像

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

输入：

输出：

第一种 循环

使用循环的思路，将每个结点的左右子树调换一下即可。使用递归收集所有结点。

public void Mirror(TreeNode root) {
        if (root == null) {
            return;
        }
        List<TreeNode> list = new ArrayList<>();
        traverse(root, list);

        for (int i = 0; i < list.size(); i++) {
            TreeNode cur = list.get(i);
            TreeNode tmp = cur.left;
            cur.left = cur.right;
            cur.right = tmp;
        }
    }

    private void traverse(TreeNode node,List<TreeNode> list) {
        if (node == null) {
            return;
        }
        list.add(node);
        traverse(node.left, list);
        traverse(node.right, list);
    }

第二种 递归处理

使用递归，代码非常简洁。 简直不可思议。 递归这算法有点悖论的意思，就是你首先要设想Mirror这个方法已经有了将一个结点及其子树镜像的能力，然后你利用这个还不存在的实现去实现你的方法。真是神奇。

public TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode tmp = root.left;
        root.left = mirrorTree(root.right);//翻转右边，然后将右子节点赋值给左子节点
        root.right = mirrorTree(tmp);//翻转左边，然后将左子节点赋值给右子节点
        return root;
    }