java面试题解LeetCode27二叉树的镜像实例

目录
  • 正文
  • 解题思路
    • 方法一：递归法
    • 方法二：辅助栈（或队列）

正文

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

例如输入：

4

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

4

/
7 2 / \ /
9 6 3 1

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

限制： 0 <= 节点个数 <= 1000

解题思路

方法一：递归法

根据二叉树镜像的定义，考虑递归遍历（dfs）二叉树，交换每个节点的左 / 右子节点，即可生成二叉树的镜像。 递归解析： 终止条件： 当节点 rootroot 为空时（即越过叶节点），则返回 nullnull ； 递推工作： 初始化节点 tmptmp ，用于暂存 rootroot 的左子节点； 开启递归 右子节点 mirrorTree(root.right)mirrorTree(root.right) ，并将返回值作为 rootroot 的 左子节点 。 开启递归 左子节点 mirrorTree(tmp)mirrorTree(tmp) ，并将返回值作为 rootroot 的 右子节点 。 返回值： 返回当前节点 rootroot ；

Q： 为何需要暂存 rootroot 的左子节点？ A： 在递归右子节点 “root.left = mirrorTree(root.right);root.left=mirrorTree(root.right);” 执行完毕后， root.leftroot.left 的值已经发生改变，此时递归左子节点 mirrorTree(root.left)mirrorTree(root.left) 则会出问题。

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        TreeNode tmp = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(tmp);
        return root;
    }
}

方法二：辅助栈（或队列）

利用栈（或队列）遍历树的所有节点 nodenode ，并交换每个 nodenode 的左 / 右子节点。 算法流程： 特例处理： 当 rootroot 为空时，直接返回 nullnull ； 初始化： 栈（或队列），本文用栈，并加入根节点 rootroot 。 循环交换： 当栈 stackstack 为空时跳出； 出栈： 记为 nodenode ； 添加子节点： 将 nodenode 左和右子节点入栈； 交换： 交换 nodenode 的左 / 右子节点。 返回值： 返回根节点 rootroot 。

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        Stack<TreeNode> stack = new Stack<>() {{ add(root); }};
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if(node.left != null) stack.add(node.left);
            if(node.right != null) stack.add(node.right);
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        return root;
    }
}

以上就是java面试题解LeetCode27二叉树的镜像实例的详细内容，更多关于java面试LeetCode二叉树镜像的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • Java数据结构之单链表的实现与面试题汇总

    目录 1 单链表 1.1 单链表介绍 1.2 单链表的实现思路分析 1.3 实现代码 2 单链表的面试题 2.1 统计单链表中有效节点数量 2.2 新浪–倒数第k个节点 2.3 腾讯–单链表的反转 2.4 百度–逆序打印单链表 1 单链表 1.1 单链表介绍 由于顺序表的插入删除操作需要移动大量的元素,影响了运行效率,因此引入了线性表的链式存储——单链表.单链表通过一组任意的存储单元来存储线性表中的数据元素,不需要使用地址连续的存储单元,因此它 不要求在逻辑上相邻的两个元素在物理位置上也相邻.

  • Java单链表的增删改查与面试题详解

    Java单链表的增删改查与面试题详解

    目录 一.单链表的增删改查 1.创建结点 2.单链表的添加操作 3.单链表的删除操作 4.单链表的有效结点的个数 二.大厂面试题 一.单链表的增删改查 1.创建结点 单链表是由结点连接而成,所以我们首先要创建结点类,用于对结点进行操作.定义data属性 表示序号,定义name属性表示结点存放的数据信息,定义next属性表示指向下一个结点.构造器只需要放入data属性和name属性,重写toString方法方便打印结点信息. public class Node { public int data;

  • Java经典面试题最全汇总208道(二)

    目录 前言 53.concurrentHashMap和HashTable有什么区别 54.HasmMap和HashSet的区别 55.请谈谈 ReadWriteLock 和 StampedLock 56.线程的run()和start()有什么区别? 57.为什么我们调用 start() 方法时会执行 run() 方法,为什么我们不能直接调用 run() 方法? 58.Synchronized 用过吗,其原理是什么? 59.JVM 对 Java 的原生锁做了哪些优化? 60.为什么 wait(),

  • Java经典面试题最全汇总208道(六)

    目录 前言 181.什么是类加载器,类加载器有哪些? 182.说一下类加载的执行过程? 183.JVM的类加载机制是什么? 184.什么是双亲委派模型? 185.怎么判断对象是否可以被回收? 186.说一下 jvm 有哪些垃圾回收算法? 187.说一下 jvm 有哪些垃圾回收器? 188.JVM栈堆概念,何时销毁对象 189.新生代垃圾回收器和老生代垃圾回收器都有哪些?有什么区别? 190.详细介绍一下 CMS 垃圾回收器? 191.简述分代垃圾回收器是怎么工作的? 192.Redis是什么?

  • Java经典面试题最全汇总208道(四)

    目录 前言 126.Spring 框架中的单例 Beans 是线程安全的么? 127.请解释 Spring Bean 的自动装配? 129.什么是 Spring Batch? 130.spring mvc 和 struts 的区别是什么? 131.请举例解释@Required 注解? 132.Spring常用注解 133.项目中是如何实现权限验证的,权限验证需要几张表 134.谈谈controller,接口调用的路径问题 135.如何防止表单重复提交 136.Spring中都应用了哪些设计模式

  • Java面试题之MD5加密的安全性详解

    目录 1.彩虹表 什么是彩虹表 2.解决方案 3.实现代码 总结 MD5 是 Message Digest Algorithm 的缩写,译为信息摘要算法,它是 Java 语言中使用很广泛的一种加密算法.MD5 可以将任意字符串,通过不可逆的字符串变换算法,生成一个唯一的 MD5 信息摘要,这个信息摘要也就是我们通常所说的 MD5 字符串.那么问题来了,MD5 加密安全吗? 这道题看似简单,其实是一道送命题,很多人尤其是一些新入门的同学会觉得,安全啊,MD5 首先是加密的字符串,其次是不可逆的,所

  • Java经典面试题最全汇总208道(三)

    目录 前言 websocket应用的是哪个协议 106.说一下 tcp 粘包是怎么产生的? 107.请列举出在 JDK 中几个常用的设计模式? 108.什么是设计模式?你是否在你的代码里面使用过任何设计模式? 110.在 Java 中,什么叫观察者设计模式(observer design pattern)? 111.使用工厂模式最主要的好处是什么?在哪里使用? 112.请解释自动装配模式的区别? 113.举一个用 Java 实现的装饰模式(decorator design pattern)?它是

  • Java经典面试题最全汇总208道(五)

    目录 前言 152.什么是 YAML? 153.如何使用 Spring Boot 实现分页和排序? 154.如何使用 Spring Boot 实现异常处理? 155.单点登录 156.Spring Boot比Spring多哪些注解 157.打包和部署 158.Spring Boot如何访问不同的数据库 159.查询网站在线人数 160.easyExcel如何实现 161.什么是 Swagger?你用 Spring Boot 实现了它吗? 162.数据库的三范式是什么? 163.一张自增表里面总共

  • Java经典面试题最全汇总208道(一)

    目录 前言 1.JDK 和 JRE 有什么区别? 2.== 和 equals 的区别是什么? 3.final 在 java 中有什么作用? 4.java 中的 Math.round(-1.5) 等于多少? 5.String 属于基础的数据类型吗? 6.String str="i"与 String str=new String(“i”)一样吗? 7.如何将字符串反转? 8.String 类的常用方法都有那些? 9.new String("a") + new Strin

  • java面试题解LeetCode27二叉树的镜像实例

    目录 正文 解题思路 方法一:递归法 方法二:辅助栈(或队列) 正文 LeetCode27. 二叉树的镜像 请完成一个函数,输入一个二叉树,该函数输出它的镜像. 例如输入: 4 /2 7 / \ /1 3 6 9 镜像输出: 4 /7 2 / \ /9 6 3 1 示例 1: 输入:root = [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1] 限制: 0 <= 节点个数 <= 1000 解题思路 方法一:递归法 根据二叉树镜像的定义,考虑递归遍历(dfs)二叉树,交换每个

  • TypeScript获取二叉树的镜像实例

    TypeScript获取二叉树的镜像实例

    目录 前言 思路分析 实现代码 前言 给定一颗二叉树,如何获取它的镜像?本文将跟大家分享这个问题的解决方案,欢迎各位感兴趣的开发者阅读本文. 思路分析 当我们把一张写有文字的纸放在镜子前面,你看到的内容正好与你写的内容是相反的.那么我们就可以依据照镜子的经验画出它的镜像了,如下所示: 镜像前后的两棵树根节点相同 镜像后的树与镜像前相比:它们的左.右子节点交换了位置 通过观察后,我们就得出了一颗树的镜像过程:先序遍历这棵树的每个节点,如果遍历到的节点有子节点,就交换它的两个子节点.当交换完所有非叶

  • Java C++题解 leetcode第k个数实例

    Java C++题解 leetcode第k个数实例

    目录 题目要求 思路一:小根堆 Java C++ 思路二:多路归并[多指针] Java C++ Rust 总结 题目要求 思路一:小根堆 中文题目描述不太清晰,但其实由题目可以发现,当x满足条件时,3x.5x.7x分别也都满足条件. 将满足条件的数依次放入优先队列存放用于后续计算,由于每次要取待计算队列中最小的数x,所以定义小根堆: 弹出x,计算3x.5x.7x并入队: 用一个哈希表记录防止重复入队. 每次取数(pop)时进行计数,到第k次结束,当前队首即为答案. Java <学到了> 1L也

  • java算法题解Leetcode15三数之和实例

    目录 题目 解题思路 题目 15. 三数之和 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组. 注意:答案中不可以包含重复的三元组. 示例 1:输入:nums = [-1,0,1,2,-1,-4]输出:[[-1,-1,2],[-1,0,1]]示例 2:输入:nums = []输出:[]示例 3:输入:nums = [0]输出:[]提示:0 <= nums.length <=

  • C++ 二叉树的镜像实例详解

    C++ 二叉树的镜像实例详解

    二叉树的镜像:将一个二叉树的左右子树,调换位置.即下图的形式: 递归的思想是: 从根节点的左右子树进行交换,然后以根节点的左子树为根节点,而后以根节点的右结点为根节点,进行左右子树交换.遇到空节点或叶节点直接返回.下面求二叉树镜像的函数代码实现: template<class T> void MirroTree(TreeNode<T> * root) { if (root == NULL) return; if (root->_left == NULL &&

  • Java编程求二叉树的镜像两种方法介绍

    Java编程求二叉树的镜像两种方法介绍

    给出一棵二叉树,求它的镜像,如下图:右边是二叉树是左边二叉树的镜像. 仔细分析这两棵树的特点,看看能不能总结出求镜像的步骤.这两棵树的根节点相同,但他们的左右两个子节点交换了位置.因此我们不妨先在树中交换根节点的两个子节点,就得到了下面一幅图中的第二颗树 解法1(递归) 思路1:如果当前节点为空,返回,否则交换该节点的左右节点,递归的对其左右节点进行交换处理. /*class TreeNode{ int val; TreeNode left=null; TreeNode right=null;

  • Java C++题解leetcode消失的两个数字实例

    Java C++题解leetcode消失的两个数字实例

    目录 题目要求 思路:数学推导 Java C++ Rust 总结 题目要求 思路:数学推导 不重复的数组序列可以根据高斯公式计算所有元素的总和: 用当前数组长度加上两个缺失的数字可以得到所有数字长度,即可应用公式. 减去当前数组和即可得到缺失数字和sumsumsum: 两个缺失的数字分别位于m=sum2m=\frac{sum}{2}m=2sum两边: 遍历当前数组中所有小于(或大于)mmm的值,找到缺失的一个: 同样利用两个“和”的差值得到: 利用sumsumsum即可得到另一个. Java c

  • java 实现最小二叉树堆排序的实例

    java 实现最小二叉堆排序的实例 写在前面: 一觉醒来,我就突然有灵感了...... 最小二叉堆定义: 二叉堆是完全二元树或者是近似完全二元树,最小二叉堆是父结点的键值总是小于或等于任何一个子节点的键值的堆堆. 存储: 二叉堆一般用数组来表示. 根节点在数组中的位置是0,第n个位置的子节点分别在2n+1和 2n+2: 位置k的叶子的父节点位置为(k-1)/2: 实现: /** * @description 元素添加到末尾,和它的父节点比,如果比它小就交换 * @param array * *

  • Java面试高频问题之RabbitMQ系列全面解析

    Java面试高频问题之RabbitMQ系列全面解析

    1.RabbitMQ是什么? RabbitMQ是一款开源的,Erlang编写的,基于AMQP(高级消息队列协议)协议的消息中间件. 2.为什么要使用消息队列? 从本质上来说是因为互联网的快速发展,业务不断扩张,促使技术架构需要不断的演进. 从以前的单体架构到现在的微服务架构,成百上千的服务之间相互调用和依赖.从互联网初期一个服务器上有 100 个在线用户已经很了不得,到现在坐拥10亿日活的微信.此时,我们需要有一个「工具」来解耦服务之间的关系.控制资源合理合时的使用以及缓冲流量洪峰等等.因此,消

  • java面试常见问题之Hibernate总结

    主要从以下十几个方面对Hibernate做总结,包括Hibernate的检索方式,Hibernate中对象的状态,Hibernate的3种检索策略是什么,分别适用于哪种场合,ORM解决的不匹配问题, Hibernate映射继承关系的3种方式,Session的find()方法以及Query接口的区别等方面问题的总结,具体内容如下: 1  Hibernate的检索方式 Ø  导航对象图检索(根据已经加载的对象,导航到其他对象.) Ø  OID检索(按照对象的OID来检索对象.) Ø  HQL检索(使

随机推荐