面试经典150题【71-80】

news/2024/5/30 2:14:39/文章来源:https://blog.csdn.net/pH2002/article/details/136570608

文章目录

  • 面试经典150题【71-80】
    • 112.路径总和
    • 129.求根节点到叶子节点的数字之和
    • 124.二叉树中的最大路径和(要思考)
    • 173.二叉树迭代搜索器
    • 222.完全二叉树节点的个数
    • 236.二叉树的最近公共祖先
    • 199.二叉树的右视图
    • 637.二叉树的层平均值
    • 102.二叉树的层序遍历
    • 103.二叉树的锯齿形层序遍历

面试经典150题【71-80】

112.路径总和

在这里插入图片描述

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if(root==null) return false;//叶子节点if(root.left ==null && root.right==null){return root.val == targetSum;}//看左子节点和右子节点,并且要减去当前值return hasPathSum(root.left,targetSum-root.val) || hasPathSum(root.right,targetSum-root.val);}
}

129.求根节点到叶子节点的数字之和

在这里插入图片描述
这种DFS的,还是要搞一个辅助函数

class Solution {public int sumNumbers(TreeNode root) {return helper(root,0);}public int helper(TreeNode root,int ans){if(root==null) return 0;int temp=ans*10+root.val;if(root.left==null && root.right==null){return temp;}return helper(root.left,temp)+helper(root.right,temp);}
}

124.二叉树中的最大路径和(要思考)

在这里插入图片描述
这个题要好好思考一下。
首先要明白,maxGain求的是什么,求的是经过我这个root节点以后,单边的最大值。因为只有这样,才能搞 root.val +maxGain(root.left) +maxGain(root.right)的值为最大。

class Solution {int maxSum = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {maxGain(root);return maxSum;}public int maxGain(TreeNode node) {if (node == null) {return 0;}// 递归计算左右子节点的最大贡献值// 只有在最大贡献值大于 0 时,才会选取对应子节点int leftGain = Math.max(maxGain(node.left), 0);int rightGain = Math.max(maxGain(node.right), 0);// 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值int priceNewpath = node.val + leftGain + rightGain;// 更新答案maxSum = Math.max(maxSum, priceNewpath);// 返回节点的最大贡献值return node.val + Math.max(leftGain,rightGain);}
}

173.二叉树迭代搜索器

中序遍历树,存到数组里即可。

222.完全二叉树节点的个数

BFS遍历一遍求节点就行。DFS直接递归也可以。
不过因为是完全二叉树,则可以判断是否完全,若是完全则直接2的n次方-1,否则就DFS,
ans = 1 + func(root.left) + func(root.right)

236.二叉树的最近公共祖先

在这里插入图片描述
要不p,q在root的两侧,要不p和q其中一个是root一个是小弟。
终止条件:

if(root == null || root == p || root == q) return root;

如果为叶子节点,自然什么都没找到。如果找到一个节点,就返回一个节点。
比如 root == p == 3 ,则直接返回3.
遍历其左右子树

TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);

如果左右子树都有值,则答案为root
如果只有一个有值,则为其中的一边。答案返回的就是最近公共祖先

if(left == null) return right;
if(right == null) return left;
return root;

199.二叉树的右视图

在这里插入图片描述
简单的BFS即可,当 i == size -1 的时候加入答案数组中。

637.二叉树的层平均值

BFS

102.二叉树的层序遍历

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {if(root==null) return new ArrayList<>();List<List<Integer>> res=new ArrayList<>();Queue<TreeNode> queue=new LinkedList<TreeNode>();queue.add(root);while(!queue.isEmpty()){int size=queue.size();List<Integer>list=new ArrayList<Integer>();for(int i=0;i<size;i++){TreeNode node=queue.poll();list.add(node.val);if(node.left!=null) queue.add(node.left);if(node.right!=null) queue.add(node.right);}res.add(list);}return res;}
}

103.二叉树的锯齿形层序遍历

设置一个boolean变量,每回合进行翻转。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1005730.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

9、组合模式(结构性模式)

组合模式又叫部分整体模式&#xff0c;它创建了对象组的树形结构&#xff0c;将对象组合成树状结构&#xff0c;以一致的方式处理叶子对象以及组合对象&#xff0c;不以层次高低定义类&#xff0c;都是结点类 一、传统组合模式 举例&#xff0c;大学、学院、系&#xff0c;它们…

guava的使用

对数组操作前判断是否会越界&#xff1a; List<String> s new ArrayList<>();System.out.println(Preconditions.checkElementIndex(2,s.size(),"下标长度超过了")); 是否为空 String s null;System.out.println(Preconditions.checkNotNull(s)); 判空…

设计模式学习系列 -- 随记

文章目录 前言 一、设计模式是什么&#xff1f; 二、设计模式的历史 三、为什么以及如何学习设计模式&#xff1f; 四、关于模式的争议 一种针对不完善编程语言的蹩脚解决方案 低效的解决方案 不当使用 五、设计模式分类 总结 前言 最近可能工作生活上的稳定慢慢感觉自己丢失…

小米公司研发岗的年终奖。。

小米 好的公司有年终且在年前发放&#xff0c;一般的公司有&#xff08;可能打折的&#xff09;年终且年后分批发放&#xff0c;不好的公司各有操作。 3 月已来&#xff0c;小米的年终也开始热议起来。 最近&#xff0c;一则「传小米年终打折&#xff0c;14薪能保住吗」冲上热搜…

修改dataV-vue3 中的组件 装饰5 decoration5 的动画重复次数

dataV-vue3 文档 装饰 5 是一个具有动画效果的 背景线框 但是开发者 没有给我们 提供 动画重复次数的 配置项&#xff0c;只提供了单次动画时长&#xff0c;如果把单词动画时长设置的很长&#xff0c;动画的延展速度也会跟着变得很慢&#xff0c;不符合预期。 使用开发者工具…

学习vue3第五节(reactive 及其相关)

1、定义 reactive() 创建一个响应式代理对象&#xff0c;不同于ref()可以创建任意类型的数据&#xff0c;而reactive()只能是对象&#xff0c;会响应式的深层次解包任何属性&#xff0c;将其标注为响应式 响应式是基于ES6的proxy实现的代理对象&#xff0c;该proxy对象与原对象…

rtthread stm32h743的使用(七)dac设备使用

我们要在rtthread studio 开发环境中建立stm32h743xih6芯片的工程。我们使用一块stm32h743及fpga的核心板完成相关实验&#xff0c;核心板如图&#xff1a; 1.我们还是先建立工程 2.生成工程后打开mx进行配置&#xff0c;时钟配置如前所讲&#xff0c;不在赘述 3.更改mx文件…

Vue3全家桶 - Vue3 - 【8】模板引用【ref】(访问模板引用 + v-for中的模板引用 + 组件上的ref)

模板引用【ref】 Vue3官网-模板引用&#xff1b;如果我们需要直接访问组件中的底层DOM元素&#xff0c;可使用vue提供特殊的ref属性来访问&#xff1b; 一、 访问模板引用 在视图元素上采用ref属性来设置需要访问的DOM元素&#xff1a; 该 ref 属性可采用 字符串 值的执行设…

浏览器的工作原理

从输入一个url到页面加载完成&#xff0c;中间都发生了什么&#xff1f; 参考原文地址 首先在浏览器地址栏输入一个地址并回车之后&#xff0c; 1. DNS查找 浏览器会进行DNS查找&#xff0c;把域名https://example.com转化为真实的IP地址10.29.33.xx&#xff0c;根据IP地址找…

Linux——权限的理解

Linux——权限的理解 文章目录 Linux——权限的理解一、shell命令以及运行原理二、Linux权限的概念切换用户对指令提权 三、Linux权限管理1. 文件访问者的分类&#xff08;人&#xff09;2. 文件类型和访问权限&#xff08;事物属性&#xff09;文件类型基本权限文件权限值的表…

Flutter第四弹:Flutter图形渲染性能

目标&#xff1a; 1&#xff09;Flutter图形渲染性能能够媲美原生&#xff1f; 2&#xff09;Flutter性能优于React Native? 一、Flutter图形渲染原理 1.1 Flutter图形渲染原理 Flutter直接调用Skia。 Flutter不使用WebView&#xff0c;也不使用操作系统的原生控件,而是…

【Web】浅聊XStream反序列化本源之恶意动态代理注入

目录 简介 原理 复现 具体分析之前 我们反序列化了个什么&#xff1f; XStream反序列化的朴素通识 具体分析 第一步&#xff1a;unmarshal解组 第二步&#xff1a;readClassType获取动态代理类的Class对象 第三步&#xff1a;调用convertAnother对动态代理类进行实例…

十六、接口隔离原则、反射、依赖注入

接口隔离原则、反射、特性、依赖注入 接口隔离原则 客户端不应该依赖它不需要的接口&#xff1b;一个类对另一个类的依赖应该建立在最小的接口上。 五种原则当中的i 上一章中的接口&#xff0c;即契约。 契约就是在说两件事&#xff0c;甲方说自己不会多要&#xff0c;乙方会在…

AWS 入门实践-远程访问AWS EC2 Linux虚拟机

远程访问AWS EC2 Linux虚拟机是AWS云计算服务中的一个基本且重要的技能。本指南旨在为初学者提供一系列步骤&#xff0c;以便成功地设置并远程访问他们的EC2 Linux实例。包括如何上传下载文件、如何ssh远程登录EC2虚拟机。 一、创建一个AWS EC2 Linux 虚拟机 创建一个Amazon…

HBuilder发行微信小程序

首先需要完善mainifest.json中的基本配置 这个需要组测dcloud才可以获取&#xff0c;注册后点击重新获取就可以。 然后发行前还需要完成dcloud的信息&#xff0c;这个他会给你网址 点击连接完成信息填写就可以了 然后就可以发行了。 发行成功后会自动跳转微信小程序&#xff…

基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的木材表面缺陷检测系统(深度学习+Python代码+UI界面+训练数据集)

摘要&#xff1a;开发高效的木材表面缺陷检测系统对于提升木材加工行业的质量控制和生产效率至关重要。本篇博客详细介绍了如何运用深度学习技术构建一个木材表面缺陷检测系统&#xff0c;并提供了完整的实现代码。该系统采用了强大的YOLOv8算法&#xff0c;并对YOLOv7、YOLOv6…

LeetCode101题:对称二叉树(python3)

对称二叉树定义&#xff1a; 对于树中 任意两个对称节点 L 和 R &#xff0c;一定有&#xff1a; L.val R.val &#xff1a;即此两对称节点值相等。 L.left.val R.right.val &#xff1a;即 L的 左子节点 和 R 的 右子节点 对称。 L.right.val R.left.val &#xff1a;即 L…

微服务之商城系统

文章目录 一、商城系统建立之前的一些配置1、nacos2、Mysql3、consul【暂时不使用consul注册服务】这个可以跳过4、redis 二、grpc环境搭建三、微服务架构使用的protobuf1、查看proto的版本号2、安装protoc-gen-go和protoc-gen-go-grpc3、生成protobuff以及grpc的文件 一、商城…

EMQX+InfluxDB+Grafana 构建物联网可视化平台

EMQXInfluxDBGrafana 构建物联网可视化平台 本文以常见物联网使用场景为例&#xff0c;介绍了如何利用 EMQ X MQTT 服务器 InfluxDB Grafana 构建物联网数据可视化平台&#xff0c;将物联网设备上传的时序数据便捷地展现出来。 在物联网项目中接入平台的设备数据和数据存储…

Hadoop生态选择(一)

一、项目框架 1.1技术选型 技术选型主要考虑因素:维护成本、总成本预算、数据量大小、业务需求、行业内经验、技术成熟度。 数据采集传输:Flume&#xff0c;Kafka&#xff0c;DataX&#xff0c;Maxwell&#xff0c;Sqoop&#xff0c;Logstash数据存储:MySQL&#xff0c;HDFS…