alt alt

//方法一：广度优先搜索（Breath FirstSearch）
//分析:遍历每一个节点，然后交换他的两个子节点，一直循环下去，直到所有的节点都遍历完为止，
//时间复杂度：n
//空间复杂度：1
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    public TreeNode Mirror (TreeNode pRoot) {
        // write code here
        //排除特殊情况
        if(pRoot == null)
            return null;
        //定义一个队列，利用队列的先进先出进行遍历
        Queue<TreeNode> queue = new LinkedList<>();
        //将根节点放入队列中
        queue.add(pRoot);
        //通过循环遍历出节点
        while(!queue.isEmpty()){
            //队列弹出先进节点，先进先出
            TreeNode node = queue.poll();
            //打印出弹出的节点
            System.out.println(node.val);
            //交换左右子树
                //暂存左子树
            TreeNode left = node.left;
                //左右交换
            node.left = node.right;
            node.right = left;
            //若左子树不为空，将交换后的左子树放入队列中
            if(node.left != null){
                queue.add(node.left);
            }
            //若右子树不为空，将交换后的右子树放入队列中
            if(node.right != null){
                queue.add(node.right);
            }
            //接下来迭代遍历，找出所有镜像后的节点
            
        }
        return pRoot;
    }
}

//方法一：深度优先搜索（Deep FirstSearch）
//分析:遍历每一个节点，然后交换他的两个子节点，一直循环下去，直到所有的节点都遍历完为止，
//时间复杂度：n
//空间复杂度：1
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    public TreeNode Mirror (TreeNode pRoot) {
        // write code here
        //排除特殊情况
        if(pRoot == null)
            return null;
        //使用栈结构:用于深度遍历（Deep FirstRearch）
        //定义一个栈
        Stack<TreeNode> stack = new Stack<>();
        //把根节点压入栈中
        stack.push(pRoot);
        
        //遍历树，交换左右子树
            //判断栈不为空
             //定义一个新引用指向栈弹出的节点
            //定义临时引用，用于左右子树的交换
            //若左子树不为空，压入栈中
            //若右子树不为空，压入栈中
            //迭代遍历
        while(!stack.empty()){
            TreeNode node = stack.pop();
            
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
            
            if(node.left != null){
                stack.push(node.left);
            }
            if(node.right != null){
                stack.push(node.right);
            }
        }
           
        //返回镜像处理后的树
        return pRoot;
    }
}

//方法三：中序遍历--非递归（前序或后序遍历都可以）
//分析:遍历每一个节点，然后交换他的两个子节点，一直循环下去，直到所有的节点都遍历完为止，
//时间复杂度：n
//空间复杂度：1
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    public TreeNode Mirror (TreeNode pRoot) {
        // write code here
        //如果为空，返回null
        if(pRoot == null)
            return null;
        //定义一个栈
        Stack<TreeNode> stack = new Stack<>();
        //在定义一个节点用于指向根节点，用于数据处理
        TreeNode node = pRoot;
        
        //循环遍历，满足栈不为空或者树不为空
        while(node != null || !stack.empty()){
            //当满足树不为空，遍历左子树并压栈
            while(node != null){
                stack.push(node);
                node = node.left;
            }
            //遍历完左子树后，

            //若栈不为空，边弹栈，弹出的节点的左右子树交换
            //边查询弹出的节点是否有右子树
            if(!stack.empty()){
                TreeNode pnode = stack.pop();

                TreeNode temp = pnode.left;
                pnode.left = pnode.right;
                pnode.right = temp;
                //注意这里以前是pnode.right，因为上面已经交换了
                //所以这里要改为pnode.left
                node = pnode.left;
            }
        }
        return pRoot;
    }
}

//方法四：中序遍历————递归
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    public TreeNode Mirror (TreeNode pRoot) {
        // write code here
        //如果为空，返回null
        if(pRoot == null)
            return null;
        
        //中序遍历————递归法
        //中序遍历左子树
        Mirror(pRoot.left);
        //根节点，左右子树交换
        TreeNode temp = pRoot.left;
        pRoot.left = pRoot.right;
        pRoot.right = temp;
        //中序遍历右子树，由于左右子树已经互换，故写left
        Mirror(pRoot.left);
        return pRoot;    //因为最上层的pRoot没有改变，递归里里的pRoot是局部变量
    }
}