字节跳动面试题之镜像二叉树2020

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9
镜像输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

实例：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

解题思路是树的广度优先遍历，这里还有一个数据交换问题，是数组数据块数据交换问题的延伸题目，有兴趣的可以去看看左神的  A B      A BA  交换问题。 

import java.util.ArrayList;
import java.util.List;

public class test7 {

    public TreeNode mirrorTree(TreeNode root) {
        if(root == null){
            return root;
        }
        List<TreeNode> list = new ArrayList<>();
        list.add(root);
        while (list.size()>0){
            List<TreeNode> newList = new ArrayList<>();
            for(int i = 0;i<list.size();i++) {
                TreeNode treeNode = list.get(i);
                TreeNode node3 = treeNode.left;
                treeNode.left = treeNode.right;
                treeNode.right = node3;
                if(treeNode.left!=null){
                    newList.add(treeNode.left);
                }
                if(treeNode.right!=null){
                    newList.add(treeNode.right);
                }
            }
            list = newList;
        }

        return root;
    }



    public static void main(String[] args) {

        test7 test7 = new test7();

        TreeNode treeNode1 = new TreeNode(4);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(7);
        TreeNode treeNode4 = new TreeNode(1);
        TreeNode treeNode5 = new TreeNode(3);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode7 = new TreeNode(9);


        treeNode1.left =treeNode2;
        treeNode1.right = treeNode3;

        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;

        treeNode3.left = treeNode6;
        treeNode3.right = treeNode7;

        TreeNode treeNode = test7.mirrorTree(treeNode1);
        System.out.println(treeNode);
    }


}

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    public  TreeNode(int x) { val = x; }
}

输出结果：