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

桃扇骨 2023-02-20 02:26 14阅读 0赞

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

例如输入：

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; }
    }

输出结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NhaTczOTI5NTczMg_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NhaTczOTI5NTczMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200622095209967.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NhaTczOTI5NTczMg==,size_16,color_FFFFFF,t_70