专栏首页五分钟学算法剑指 Offer 27. 二叉树的镜像

剑指 Offer 27. 二叉树的镜像

大家好,我是程序员吴师兄,欢迎来到 图解剑指 Offer 结构化专栏,在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码,希望能帮助你即使在面试的时候紧张也能做对。

AlgoMooc 算法慕课网,每道题目都有动画和图片,致力于帮助每个程序员通过算法面试!

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列面试题 27. 二叉树的镜像。

题目汇总链接:https://www.algomooc.com/jianzhioffer

一、题目描述

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

二叉树

示例 1:

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

限制:

  • 0 <= 节点个数 <= 1000

二、题目解析

我们依旧用 四步分析法 进行结构化的分析。

  • 模拟:模拟题目的运行。
  • 规律:尝试总结出题目的一般规律和特点。
  • 匹配:找到符合这些特点的数据结构与算法。
  • 边界:考虑特殊情况。

1、模拟

二叉树的镜像指的是对于二叉树内任意一个节点,都交换了它的左右子节点。

比如下面这颗三层七节点的二叉树,首先交换左右子树。

交换后的左右子树的子节点还是保持原来的顺序,需要去交换左右子树自己的左右子树。

2、规律

直接利用递归遍历二叉树,交换每个节点的左 / 右子节点,即可生成二叉树的镜像。

3、匹配

  • 递归

4、边界

  • 二叉树为空

三、动画描述

https://www.algomooc.com/438.html

四、图片描述

剑指 Offer 27. 二叉树的镜像.002

剑指 Offer 27. 二叉树的镜像.003

剑指 Offer 27. 二叉树的镜像.004

剑指 Offer 27. 二叉树的镜像.005

剑指 Offer 27. 二叉树的镜像.006

剑指 Offer 27. 二叉树的镜像.007

剑指 Offer 27. 二叉树的镜像.008

剑指 Offer 27. 二叉树的镜像.009

剑指 Offer 27. 二叉树的镜像.010

剑指 Offer 27. 二叉树的镜像.011

剑指 Offer 27. 二叉树的镜像.012

剑指 Offer 27. 二叉树的镜像.013

剑指 Offer 27. 二叉树的镜像.014

剑指 Offer 27. 二叉树的镜像.015

剑指 Offer 27. 二叉树的镜像.016

剑指 Offer 27. 二叉树的镜像.017

剑指 Offer 27. 二叉树的镜像.018

剑指 Offer 27. 二叉树的镜像.019

五、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        // 当节点为空时,直接返回
        if(root == null) return null;
        // 设置一个临时的节点 tmp 用来存储当前节点的左子树
        TreeNode tmp = root.left;
        // 以下两个操作是在交换当前节点的左右子树

        // 当前节点的左子树为节点的右子树
        // 同时递归下去,不停的交互子树中的节点
        root.left = mirrorTree(root.right);

        // 当前节点的右子树为节点的左子树
        // 同时递归下去,不停的交互子树中的节点
        root.right = mirrorTree(tmp);

        // 最后返回根节点
        return root;
    }
}

六、复杂度分析

时间复杂度

时间复杂度为 O(N)。

空间复杂度

空间复杂度为 O(N)。

七、相关标签

  • 递归

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu),作者:程序员吴师兄

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-06-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【剑指Offer】27. 二叉树的镜像

    瑞新
  • LeetCode 剑指Offer 面试题27. 二叉树的镜像

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

    TrueDei
  • 剑指Offer-二叉树的镜像

    package Tree; import java.util.ArrayDeque; import java.util.ArrayList; import j...

    武培轩
  • 【剑指Offer】二叉树的镜像

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

    小新哟
  • 【剑指offer】二叉树的镜像

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 剑指offer--二叉树的镜像

    题目描述 操作给定的二叉树,将其变换为源二叉树的镜像。 输入描述: 二叉树的镜像定义:源二叉树 8 ...

    AI那点小事
  • 【剑指Offer】二叉树的镜像

    Rochester
  • 【剑指offer】33.二叉树镜像

    可以看到首先对根节点的左右进行翻转。 再递归的对左子树,以及右子树进行翻转。 之前讲过,链表的题目分为四个步骤:连过来、指针走、断后路、调状态。 二涉及到树的...

    Leetcode名企之路
  • 剑指offer - 二叉树的镜像 - JavaScript

    心谭博客
  • 剑指offer打卡6:二叉树镜像

    在上题中我说了对于与二叉树有关的题目,90% 是采取递归的方式来解决比较简单的。而且解法还都非常相似,没看过上道题的或许可以看一下:剑指offer打卡5:二叉树...

    帅地
  • 每日一题 剑指offer(二叉树镜像)

    编程是很多偏计算机、人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”,通过每天一道编程题目来强化...

    小白学视觉
  • 剑指Offer面试题:18.二叉树的镜像

    Step1.先序遍历原二叉树的每个节点,如果遍历到的结点有子结点,就交换它的两个子结点。

    Edison Zhou
  • 每天一道剑指offer-二叉树的镜像

    今天的题目 每天的题目见github(看最新的日期): https://github.com/gzc426 具体的题目可以去牛客网对应专题去找。

    乔戈里
  • 【剑指offer】5.二叉树的镜像和打印

    ConardLi
  • 剑指Offer系列刷题笔记汇总

    版权声明:本文为博主原创文章,未经博主允许不得转载。个人网站:http://cuijiahua.com。 ...

    Jack_Cui
  • LeetCode 226. 翻转二叉树(DFS & BFS)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/invert-binary-tree 著作权归领扣网...

    Michael阿明
  • 两分钟弄懂对称二叉树

    大家好呀,我是吴师兄,今天照例来更新一道 LeetCode 算法题,根据以往数据来看,这类文章的打开率普遍不高,一般在三四千左右,远远低于水文或者热点文一两万的...

    五分钟学算法
  • Day68:剑指Offer总结

      本人花了两个月时间刷完了牛客网带上的剑指Offer,一共67题。本人是从4月21日开始刷题,每天一题,截止到7月6日已经全部刷完。这67题均是考察的数据结构...

    一计之长
  • 牛客网剑指offer java 全部题解

    https://mp.weixin.qq.com/s?__biz=MzI5MzYzMDAwNw==&mid=2247485570&idx=2&sn=bcde8b...

    乔戈里

扫码关注云+社区

领取腾讯云代金券