剑指18.二叉树的镜像

题目描述

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

思路

先 前序或层序遍历 这棵树的每个节点，如果遍历到的节点有子节点，就交换它的两个子节点。当交换完所有非叶节点的左右节点之后，就得到了树的镜像。

既然是二叉树的遍历，那么就有 递归实现 和 非递归实现 两个版本 ~

 

解法1（递归实现）

/**
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;
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        if(root.left != null)
            Mirror(root.left);
        if(root.right != null)
            Mirror(root.right);
    }
}

解法2（非递归前序遍历）

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

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

    }

}
*/
// 非递归前序遍历（借助栈结构）
import java.util.Stack;
public class Solution {
    public void Mirror(TreeNode root) {
        if(root == null)
            return;
        if(root.left == null && root.right == null)
            return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();  //每次从堆栈中弹出栈顶元素，表示当前访问的元素
            TreeNode temp = cur.left;
            cur.left = cur.right;
            cur.right = temp;
            if(cur.right != null)//先压栈右子树，因为先压栈的后弹出，左子树需要先访问
                stack.push(cur.right);
            if(cur.left != null)
                stack.push(cur.left);
        }
    }
}

解法3（非递归层序遍历）

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

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

    }

}
*/
// 非递归层序遍历（借助队列结构）
import java.util.Queue;
import java.util.LinkedList;
public class Solution {
    public void Mirror(TreeNode root) {
        if(root == null)
            return;
        if(root.left == null && root.right == null)
            return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root); //1.先将树的根结点放入到队列中
        while(!queue.isEmpty()){
            //2.计算每层的结点数目，也就是队列中的元素
            int levelnums = queue.size();
            //3.遍历一层的所有结点
            //Note：不加for循环也可以，加for循环可以求层数 / 求出每层多少个节点
            for(int i = 0; i < levelnums; i++){
                TreeNode cur = queue.poll();
                TreeNode temp = cur.left;
                cur.left = cur.right;
                cur.right = temp;
                if(cur.left != null) queue.offer(cur.left);
                if(cur.right != null) queue.offer(cur.right);
            }
            /*TreeNode cur = queue.poll();
            TreeNode temp = cur.left;
            cur.left = cur.right;
            cur.right = temp;
            if(cur.left != null)  //队列先进先出
                queue.offer(cur.left);
            if(cur.right != null)
                queue.offer(cur.right);*/
        }
    }
}

参考：

非递归遍历二叉树Java实现

☆☆☆LeetCode二叉树的层序遍历系列问题总结（队列实现）https://blog.csdn.net/u014116780/article/details/82978934