当前位置: 首页 > news >正文

【牛客面试必刷TOP101】Day8.BM33 二叉树的镜像和BM36 判断是不是平衡二叉树

作者简介:大家好,我是未央;

博客首页:未央.303

系列专栏:牛客面试必刷TOP101

每日一句:人的一生,可以有所作为的时机只有一次,那就是现在!!!!

文章目录

前言

一、二叉树的镜像

题目描述

题目解析

二、判断是不是平衡二叉树

题目描述

题目解析:

总结



前言


一、二叉树的镜像

题目描述

描述:
操作给定的二叉树,将其变换为源二叉树的镜像。


数据范围:二叉树的节点数 0≤n≤1000 , 二叉树每个节点的值 0≤val≤1000;

要求: 空间复杂度 O(n) 。本题也有原地操作,即空间复杂度O(1) 的解法,时间复杂度 O(n)


举例说明:

源二叉树:

镜像二叉树:


示例1:


示例2:

题目解析

题目的主要信息:

将二叉树镜像,即将其所有左右子树交换

我们可以考虑自底向上依次交换二叉树的左右节点。


解题思路:

因为我们需要将二叉树镜像,意味着每个左右子树都会交换位置,如果我们从上到下对遍历到的节点交换位置,但是它们后面的节点无法跟着他们一起被交换,因此我们可以考虑自底向上对每两个相对位置的节点交换位置,这样往上各个子树也会被交换位置。

自底向上的遍历方式,我们可以采用后序递归的方法。


解题步骤:

  • step 1:先深度最左端的节点,遇到空树返回,处理最左端的两个子节点交换位置。
  • step 2:然后进入右子树,继续按照先左后右再回中的方式访问。
  • step 3:再返回到父问题,交换父问题两个子节点的值。

代码编写:

二、判断是不是平衡二叉树

题目描述

描述:

输入一棵节点数为 n 二叉树,判断该二叉树是否是平衡二叉树。


平衡二叉树的定义:

可定义为或者是一棵空树,

或者是具有下列性质的二叉树:

1.左子树和右子树均为平衡二叉树;

2.左子树和右子树的高度差的绝对值不超过1


注意:平衡二叉树一定是二叉排序树。含有n个结点的平衡二叉树的最大深度为O(log2(n)),即平衡二叉树的平均查找长度为O(log2(n))


举例说明:
平衡二叉树:

非平衡二叉树:


样例解释:

样例二叉树如图,为一颗平衡二叉树

注:我们约定空树是平衡二叉树。


数据范围:n≤100,树上节点的val值满足 0≤n≤1000;

要求:空间复杂度O(1),时间复杂度 O(n);


输入描述:

输入一棵二叉树的根节点;

返回值描述:

输出一个布尔类型的值;


示例1:


示例2:

题目解析:

从题中给出的有效信息:

  • 左右两个子树的高度差的绝对值不超过1
  • 左右两个子树都是一棵平衡二叉树

故此 首先想到的方法是使用递归的方式判断子节点的状态;


解题思路:

平衡二叉树任意节点两边的子树深度相差绝对值不会超过1,且每个子树都满足这个条件,那我们可以对每个节点找到两边的深度以后:


判断是否两边相差绝对值超过1:


然后因为每个子树都满足这个条件,我们还需要遍历二叉树每个节点当成一棵子树进行判断,而对于每个每个节点判断后,其子节点就是子问题,因此可以用递归。

IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);


解题步骤:

  • step 1:第一个函数递归遍历二叉树所有节点。
  • step 2:对于每个节点判断,调用第二个函数获取子树深度。
  • step 3:第二个函数递归获取子树深度,只需要不断往子节点深度遍历,累加左右深度的较大值。
  • step 4:根据深度判断该节点下的子树是否为平衡二叉树。

代码编写:

总结

http://www.lryc.cn/news/192080.html

相关文章:

  • CSS padding(填充)
  • C语言达到什么水平才能从事单片机工作
  • Java架构师理解SAAS和多租户
  • 关于Java线程池相关面试题
  • ExcelBDD Python指南
  • 基于深度学习的驾驶员疲劳监测系统的设计与实现
  • B树、B+树详解
  • 使用hugging face开源库accelerate进行多GPU(单机多卡)训练卡死问题
  • IDEA 修改插件安装位置
  • 牛客网SQL160
  • HDFS Java API 操作
  • 论文阅读之【Is GPT-4 a Good Data Analyst?(GPT-4是否是一位好的数据分析师)】
  • 【数据结构】:二叉树与堆排序的实现
  • 纯css手写switch
  • PyTorch 深度学习之处理多维特征的输入Multiple Dimension Input(六)
  • LeetCode【438】找到字符串中所有字母异位词
  • 关于LEFT JOIN的一次理解
  • 各报文段格式集合
  • 【算法-动态规划】最长公共子序列
  • 区块链游戏的开发流程
  • 目标检测网络系列——YOLO V2
  • 15. Java反射和注解
  • pdf处理工具 Enfocus PitStop Pro 2022 中文 for mac
  • 微信小程序入门开发教程
  • php函数
  • 3.3 封装性
  • Redis魔法:点燃分布式锁的奇妙实现
  • iOS 项目避坑:多个分类中方法重复实现检测
  • 【003】EIS数据分析_#LIB
  • Sprint framework Day07:注解结合 xml 配置