18 图解剑指Offer 二叉树的镜像 Java题解

短命女 2023-02-20 13:49 12阅读 0赞

### 18 图解剑指Offer 二叉树的镜像 Java题解 ###

*  18 图解剑指Offer 二叉树的镜像 Java题解
 *   *   *  题目链接
         *  题目描述
         *  题解:
         *  图解:
         *  代码:
         *  复杂度

# 18 图解剑指Offer 二叉树的镜像 Java题解 #

### [题目链接][Link 1] ###

### 题目描述 ###

操作给定的二叉树，将其变换为源二叉树的镜像。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3_size_16_color_FFFFFF_t_70]

### 题解: ###

1.当二叉树根节点为null，或没有叶子节点的时候直接return;  
2. 创建一个temp临时节点，二叉树左右节点交换。  
3.如果root.left != null root.left = Mirror(root.left)  
4.如果root.right!= null root.right= Mirror(root.right)  
5.树的问题一般可以用子树递归的思想解决

### 图解: ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3_size_16_color_FFFFFF_t_70 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);
        }
    }

### 复杂度 ###

空间复杂度: 空间复杂度为O(1)  
最坏时间复杂度: 递归时间复杂度O( logn)

[Link 1]: https://www.nowcoder.com/practice/564f4c26aa584921bc75623e48ca3011?tpId=13&tags=&title=&diffculty=0&judgeStatus=0&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200627193501221.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200627193611410.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MDcyNjA3,size_16,color_FFFFFF,t_70