27.二叉树的镜像

二叉树的镜像.png

• 思路:
  (1) 我们可以发现交换的是所有的非叶子节点而不是节点的值，因此使用先序遍历的方法遍历所有非叶子节点(该节点只要有孩子节点就是非叶子节点)。
  (2) 层序打印二叉树的节点,创建一个ArrayList集合用于存放打印的节点的值，创建Queue队列,使得二叉树节点入队,再根据出入队的原则实现层序遍历。
  具体代码如下:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @program: soft_test
 * @description: 二叉树的镜像
 * @author: Mr.zuo
 * @create: 2021-01-11 11:15
 **/

public class MirrorTree {
    static int[] arr = new int[7];
    static int i = 0;
    public static void main(String[] args) {

        TreeNode node = new TreeNode(4);
        node.left = new TreeNode(2);
        node.right = new TreeNode(7);
        node.left.left = new TreeNode(1);
        node.left.right = new TreeNode(3);
        node.right.left = new TreeNode(6);
        node.right.right= new TreeNode(9);
        ArrayList<Integer> result = print(node);
        for (Integer value: result) {
            System.out.print(value+" ");
        }
        System.out.println();
        TreeNode treeNode = mirrorTree(node);
        ArrayList<Integer> newRes = print(treeNode);
        for (Integer value: newRes) {
            System.out.print(value+" ");
        }
    }

    /**
     * 前序遍历二叉树,交换左右子节点
     * */
    public static TreeNode mirrorTree(TreeNode root){
        if (root == null || (root.left == null && root.right == null)){
            return root;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        if (root.left != null){
            mirrorTree(root.left);
        }
        if (root.right != null){
            mirrorTree(root.right);
        }
        return root;
    }
    public static ArrayList<Integer> print(TreeNode node){
        // 创建list集合用于存放数的节点的值
        ArrayList<Integer> list = new ArrayList<>();
        if (node == null){
            return list;
        }
        // 创建队列
        Queue<TreeNode> queue = new LinkedList<>();
        // 头结点入队
        queue.add(node);
        // 遍历队内元素
        while (queue.size() != 0){
            // 检查并删除队头元素
            TreeNode temp = queue.poll();
            // 队头元素加入List集合中
            list.add(temp.val);
            if (null != temp.left){
                // 左子树不为空
                    queue.add(temp.left);
            }
            if (null != temp.right){
                // 右子树不为空
                queue.add(temp.right);
            }
        }
        return list;
    }
}

public class TreeNode {
    // 节点的值
    int val;
    // 左子树
    TreeNode left;
    // 右子树
    TreeNode right;
    TreeNode(int val){
        this.val = val;
    }
}