大家好,我是程序员吴师兄,欢迎来到 图解剑指 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、边界

  • 二叉树为空

三、动画描述

隐藏内容
  • 普通用户购买价格:5积分
  • 会员用户购买价格:免费
  • 永久会员用户购买价格:免费推荐

四、图片描述

剑指 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)。

七、相关标签

  • 递归

发表评论

邮箱地址不会被公开。 必填项已用*标注