JZ27 二叉树的镜像

描述

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

数据范围：二叉树的节点数  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}

 说明：

如题面所示    

示例2

输入：

{}

 返回值：

{}

最简单的思路 层序遍历 每次poll后的 *** 作为交换左右子树
注意: 是直接 *** 作给定的二叉树

我的代码：(层序遍历)

    public TreeNode Mirror (TreeNode pRoot) {//同步层序遍历
        if(pRoot==null) return null;
        TreeNode ans=pRoot;
        Queue q1=new LinkedList<>();
        q1.add(pRoot);
        while (!q1.isEmpty()){
            TreeNode p1 = q1.poll();
            TreeNode t=p1.left;//交换左右子树
            p1.left=p1.right;
            p1.right=t;
            if(p1.left!=null) q1.add(p1.left);
            if(p1.right!=null) q1.add(p1.right);
        }
        return ans;
    }

递归写法：（先序/后序遍历等）

BFS层序遍历可以，其他遍历可不可以呢？试试吧DFS吧，答案果然就是

1、先序DFS （大胆写 递归真的是需要大量经验啊 不然写完对的都不敢提交）

    public TreeNode Mirror (TreeNode pRoot) {
         if(pRoot==null) return null;
        TreeNode t=pRoot.left;
        pRoot.left=pRoot.right;
        pRoot.right=t;
        pRoot.left=Mirror(pRoot.left);
        pRoot.right=Mirror(pRoot.right);
        return pRoot;
    }

2、后序DFS

    public TreeNode Mirror (TreeNode pRoot) {
       if(pRoot==null) return null;
        TreeNode left = Mirror(pRoot.left);
        TreeNode right = Mirror(pRoot.right);
        pRoot.left=right;
        pRoot.right=left;
        return pRoot;
    }