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

训练营day17

110.平衡二叉树

力扣题目链接

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

110.平衡二叉树

 

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

110.平衡二叉树1

 返回 false 。

  • 二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数。
  • 二叉树节点的高度:指从该节点到叶子节点的最长简单路径边的条数。

但leetcode中强调的深度和高度很明显是按照节点来计算的,如图:

110.平衡二叉树2

 

var isBalanced=function(root){if(root===null) return true;if(Math.abs(getHeight(root.left)-getHeight(root.right))>1) return false;return isBalanced(root.left)&&isBalanced(root.right);
}
var getHeight=function(root){if(root===null) return 0;return Math.max(getHeight(root.left),getHeight(root.right))+1;
}
// 代码随想录
// 递归法:
var isBalanced = function(root) {//还是用递归三部曲 + 后序遍历 左右中 当前左子树右子树高度相差大于1就返回-1// 1. 确定递归函数参数以及返回值const getDepth = function(node) {// 2. 确定递归函数终止条件if(node === null) return 0;// 3. 确定单层递归逻辑let leftDepth = getDepth(node.left); //左子树高度// 当判定左子树不为平衡二叉树时,即可直接返回-1if(leftDepth === -1) return -1;let rightDepth = getDepth(node.right); //右子树高度// 当判定右子树不为平衡二叉树时,即可直接返回-1if(rightDepth === -1) return -1;if(Math.abs(leftDepth - rightDepth) > 1) {return -1;} else {return 1 + Math.max(leftDepth, rightDepth);}}return !(getDepth(root) === -1);
};
// 迭代法:
// 获取当前节点的高度
//getHeight函数的作用是获取当前节点的高度
var getHeight = function (curNode) {let queue = [];if (curNode !== null) queue.push(curNode); // 压入当前元素let depth = 0, res = 0;while (queue.length) {let node = queue[queue.length - 1]; // 取出栈顶if (node !== null) {queue.pop();queue.push(node);   // 中queue.push(null);depth++;node.right && queue.push(node.right);   // 右node.left && queue.push(node.left);     // 左} else {queue.pop();node = queue[queue.length - 1];queue.pop();depth--;}res = res > depth ? res : depth;}return res;
}
var isBalanced = function (root) {if (root === null) return true;let queue = [root];while (queue.length) {let node = queue[queue.length - 1]; // 取出栈顶queue.pop();    if (Math.abs(getHeight(node.left) - getHeight(node.right)) > 1) {return false;}node.right && queue.push(node.right);node.left && queue.push(node.left);}return true;
};

257. 二叉树的所有路径

力扣题目链接(opens new window)

给定一个二叉树,返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

257.二叉树的所有路径1

 257.二叉树的所有路径

 

var binaryTreePaths = function(root) {if(root===null) return [];if(root.left===null&&root.right===null) return [root.val.toString()];let left_paths=binaryTreePaths(root.left);let right_paths=binaryTreePaths(root.right);let paths=[];for(let path of left_paths){paths.push(root.val.toString()+"->"+path);}for(let path of right_paths){paths.push(root.val.toString()+"->"+path);}return paths;
}
// 代码随想录
// 递归法
var binaryTreePaths = function(root) {//递归遍历+递归三部曲let res = [];//1. 确定递归函数 函数参数const getPath = function(node,curPath) {//2. 确定终止条件,到叶子节点就终止if(node.left === null && node.right === null) {curPath += node.val;res.push(curPath);return;}//3. 确定单层递归逻辑curPath += node.val + '->';node.left && getPath(node.left, curPath);node.right && getPath(node.right, curPath);}getPath(root, '');return res;};
//  迭代法:
var binaryTreePaths = function(root) {if (!root) return [];const stack = [root], paths = [''], res = [];while (stack.length) {const node = stack.pop();let path = paths.pop();if (!node.left && !node.right) { // 到叶子节点终止, 添加路径到结果中res.push(path + node.val);continue;}path += node.val + '->';if (node.right) { // 右节点存在stack.push(node.right);paths.push(path);}if (node.left) { // 左节点存在stack.push(node.left);paths.push(path);}}return res;};  
  • #404.左叶子之和

    力扣题目链接

 计算给定二叉树的所有左叶子之和。

404.左叶子之和1

 

var sumOfLeftLeaves=function(root){if(root===null) return 0;let sum=0;if(root.left!==null&&root.left.left===null&&root.left.right===null){sum+=root.left.val;}sum+=sumOfLeftLeaves(root.left);sum+=sumOfLeftLeaves(root.right);return sum;
}
// 代码随想录
// 递归法
var sumOfLeftLeaves = function(root) {//采用后序遍历 递归遍历// 1. 确定递归函数参数const nodesSum = function(node) {// 2. 确定终止条件if(node === null) {return 0;}let leftValue = nodesSum(node.left);let rightValue = nodesSum(node.right);// 3. 单层递归逻辑let midValue = 0;if(node.left && node.left.left === null && node.left.right === null) {midValue = node.left.val;}let sum = midValue + leftValue + rightValue;return sum;}return nodesSum(root);
};
// 迭代法
var sumOfLeftLeaves = function(root) {//采用层序遍历if(root === null) {return null;}let queue = [];let sum = 0;queue.push(root);while(queue.length) {let node = queue.shift();if(node.left !== null && node.left.left === null && node.left.right === null) {sum+=node.left.val;}node.left && queue.push(node.left);node.right && queue.push(node.right);}return sum;};

相关文章:

训练营day17

110.平衡二叉树 力扣题目链接 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 返回 true 。 示…...

Nodejs原型链污染

Nodejs与JavaScript和JSON 有一些人在学习JavaScript时会分不清Nodejs和JavaScript之间的区别,如果没有node,那么我们的JavaScript代码则由浏览器中的JavaScript解析器进行解析。几乎所有的浏览器都配备了JavaScript的解析功能(最出名的就是…...

【Vue3】element-plus中el-tree的递归处理赋值回显问题

目录一:先获取所有权限tree二:在获取所有该角色能有的权限tree三:递归处理勾选tree节点由于项目是从0-1开始构建的 rbac都需要重新构建对接 所以涉及到了权限管理和菜单管理 一级菜单包含多个二级菜单 若二级不全选,则一级显示 半…...

C语言---宏

专栏:C语言 个人主页:HaiFan. 专栏简介:本专栏主要更新一些C语言的基础知识,也会实现一些小游戏和通讯录,学时管理系统之类的,有兴趣的朋友可以关注一下。 #define预处理预定义符号define#define定义标识符…...

算法导论—路径算法总结

图算法 单源最短路径 Bellman-Ford算法: 顶点为V,边为E的图 对每条边松弛|V|-1次边权可以为负值若存在一个可以从源结点到达的权值为负值的环路,算法返回False时间复杂度:O(VE) 有向无环图单源最短路径 DAG-SHORTEST-PATHS …...

程序环境--翻译+执行

ANSI C标准下,有两种程序环境。 第1种是翻译环境,在这个环境中源代码被转换为可执行的机器指令。 翻译环境包括:预处理(预编译)编译汇编链接。四个步骤。 第2种是执行/运行环境,它用于实际执行代码。 链接…...

微信小程序内部那些事

微信小程序没有window、document,它更像是一个类似 Node.js 的宿主环境。因此在小程序内部不能使用 document.querySelector 这样的选择器,也不支持 XMLHttpRequest、location、localStorage 等浏览器 API,只能使用小程序自己提供的 API&…...

这是从零在独自开开发,将是副业赚钱最好的平台!

文章目录最重要的事情放前面1.前言2.简单介绍一下3.【独自开】介绍3.1 分层标准化平台架构3.2 集成第三方数字接口3.3 支持各个行业的系统定制开发4.如何在【独自开】赚钱获取收益?4.1 如何称为【独自开】开发者?最重要的事情放前面 通过平台的审核也可以得到相应的奖金&…...

Spring MVC 之获取参数(对象、JSON格式数据、URL地址参数、文件、Cookie)

文章目录1. 获取单个参数2. 获取多个参数3. 获取对象4. 后端参数重命名 RequestParam5. 接收 JSON 格式的数据 RequestBody6. 从 URL 地址中获取参数 PathVariable7. 上传文件 RequestPart8. 获取Cookie (CookieValue)/Session/header8.1 获取 Request 和 Response 对象8.2 获取…...

永磁同步电机中BEMF电阻的作用

一、电路原理图 二、原理分析 如图一我们测的是相电压,从理论上我们知道我们测得相电压是一个马鞍波形,马鞍波形中并没有隐含 转子的位置和速度信息。那么为什么我们还要有这样一个电路呢? 这个问题其实困惑了我好久?直到有一天…...

JAVA练习45-二叉树的层序遍历

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 前言 提示:这里可以添加本文要记录的大概内容: 提示:以下是本篇文章正文内容,下面案例可供参考 一、题目二叉树的层序遍历 …...

超高精度PID调节器的特殊功能(3)——变送输出(转发)功能及其应用

摘要:变送输出是高级PID控制器的一项重要扩展功能,可用于多区控制、串级控制、比值控制和差值控制以及数据采集及记录。为展示变送输出功能的强大作用,本文主要针对超高精度VPC 2021系列PID控制器,介绍了变送输出的具体功能、参数…...

【C++】nullptr C++中的空指针(C++11)

前言 在平时我们写C/C代码时你可能会看到有人使用NULL表示空指针,也有人用nullptr表示空指针,那么你可能会很好奇它们都是空指针吗?为什么空指针有两种写法?下面就带你了解这背后的原理。 我们都知道NULL是C语言中的空指针&#x…...

笔试题-2023-大疆-数字IC设计【纯净题目版】

回到首页:2023 数字IC设计秋招复盘——数十家公司笔试题、面试实录 推荐内容:数字IC设计学习比较实用的资料推荐 题目背景 笔试时间:2022.08.07应聘岗位:数字IC设计笔试平台:赛码题目评价 难易程度:★★★★★知识覆盖:★★★☆☆超纲范围:★★★☆☆值得一刷:★★★…...

Python dict字典方法完全攻略(全)

我们知道,Python 字典的数据类型为 dict,我们可使用 dir(dict) 来查看该类型包含哪些方法,例如: >>> dir(dict) [clear, copy, fromkeys, get, items, keys, pop, popitem, setdefault, update, values] keys()、value…...

用“AI“挑选一件智慧礼物

在久违的烟火气回归之际,充满希望的生活可能就从精心挑选一件新年礼物开始。在罗列礼品清单时,你会想到 “数据”也是其中之一吗?事实上,几乎所有时下最受欢迎的带有“智能”一词的设备,都是由大量高质量的数据创建。我…...

【Spark分布式内存计算框架——Spark Core】4. RDD函数(下) 重分区函数、聚合函数

重分区函数 如何对RDD中分区数目进行调整(增加分区或减少分区),在RDD函数中主要有如下三个函数。 1)、增加分区函数 函数名称:repartition,此函数使用的谨慎,会产生Shuffle。 2)、…...

智能工厂自动化设备如何将数据采集到物联网云平台上

制造业工厂在进行生产管理、数字化转型升级的过程中,大量自动化设备的数据采集上云一直是困扰厂商的难题之一。因设备种类多、工艺复杂、设备老旧无多余通信接口导致数据无法集中、工艺无法实时管控,加上设备服务商的本地支持比较有限,因此设…...

SpringBoot整合Mybatis的核心原理

0. 前言:1. 自动配置类MybatisAutoConfiguration:1.1. SqlSessionFactory的生成:1.2. Mapper的扫描和代理生成:1.2.1. MapperScannerConfigurer1.2.2. MapperFactoryBean1.2.3. getMapper生成代理对象2. 小结:0. 前言&…...

滴滴一面:order by 调优10倍,思路是啥?

背景说明: Mysql调优,是大家日常常见的调优工作。 所以,Mysql调优是一个非常、非常核心的面试知识点。 在40岁老架构师 尼恩的读者交流群(50)中,其相关面试题是一个非常、非常高频的交流话题。 近段时间,有小伙伴面…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

uniapp中使用aixos 报错

问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...