二叉树的镜像

考点：树

题目描述

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

输入描述:

image.png

代码格式

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public void Mirror(TreeNode root) {
        
    }
}

解题一-递归

1.思路
（由图可以发现，交换树的所在层上左右结点就可以得到镜像二叉树。类似于数组的元素交换（运用临时节点temp）。如上图中第二层中：交换树的左右子树的根结点；第三层交换左子树的左结点和右子树的右节点，左子树的右结点和右子树的左结点···这里运用递归）
具体步骤：
（1）交换左右子树；
（2）递归左右子树的镜像；
（3）当结点为叶结点时结束递归
2.代码实现

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public void Mirror(TreeNode root) {
//如果根结点为空，无需处理
        if(root==null){
            return;
        }
//左子结点和右子结点为空，无需处理
        if(root.left==null&& root.right==null){
            return;
        }
        //递归左右子树镜像
//左子结点不为空。则对该左子结点做镜像处理
        if(root.left!=null){
            Mirror(root.left);
        }
//右子结点不为空，则对该右子结点做镜像处理
        if(root.right!=null){
            Mirror(root.right);
        }
        //交换左右子树
        TreeNode temp=root.left;
        root.left=root.right;
        root.right=temp;      
    }
}

解题二-非递归（利用队列）

1.思路
利用二叉树的广度优先搜索（BFS ）
2.代码

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    public void Mirror(TreeNode root) {
        if(root==null){
            return;
        }
        if(root.left==null&& root.right==null){
            return;
        }
        Queue<TreeNode> nodes=new LinkedList<>();//定义队列
        TreeNode cur,temp;
        nodes.offer(root);//把根结点添加到队列中
        //循环判断
        while(!nodes.isEmpty()){
            int len=nodes.size(); //定义队列的长度
            for(int i=0;i<len;i++){
                cur=nodes.poll(); //返回第一个元素，并在队列中删除
                //左右结点交换
                temp=cur.left;
                cur.left=cur.right;
                cur.right=temp;
                if(cur.left!=null){
                    nodes.offer(cur.left); //把左结点放入队列中
                }
                if(cur.right!=null){
                    nodes.offer(cur.right);
                }
            }
            
        }
    }
}

知识点补充

offer，add 区别：
一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，多出的项就会被拒绝。
这时新的 offer 方法就可以起作用了。它不是对调用 add() 方法抛出一个 unchecked 异常，而只是得到由 offer() 返回的 false。
poll，remove 区别：
remove() 和 poll() 方法都是从队列中删除第一个元素。remove() 的行为与 Collection 接口的版本相似， 但是新的 poll() 方法在用空集合调用时不是抛出异常，只是返回 null。因此新的方法更适合容易出现异常条件的情况。
peek，element区别：
element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null。