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

代码随想录Day14 LeetCodeT110平衡二叉树 T257二叉树的所有路径 T404 左叶子之和

 以下思路来自于: 代码随想录 (programmercarl.com)

LeetCode T110 平衡二叉树

题目链接:110. 平衡二叉树 - 力扣(LeetCode)

题目思路

前面我们说过了,求二叉树的深度我们应该使用前序遍历,求二叉树的高度我们应该使用后序遍历,因为后序遍历可以将子树的高度返回给父节点,这样层层递归就能得到答案,而深度是从根节点下去一直到空节点为止,这里清楚了这个逻辑,我们就可以来做这道题了,我们知道一个平衡二叉树的高度差是小于等于1的,而不是平衡二叉树的话只需任意子树的高度大于即可,这里我们仍然使用递归完成

1.确定参数和返回值

求高度,返回值是int 只需传入一个节点即可

int getHeight(TreeNode node)

2.确定终止条件

这里我们遇到空节点处即可返回

if(node == null){return 0;}

3.确定一次递归逻辑

我们默认如果不是平衡二叉树就返回-1即可,我们按照左右根进行遍历

注:每次获取完左右子树记得判断一次

        int leftHeight = getHeight(node.left);if(leftHeight == -1){return -1;}int rightHeight = getHeight(node.right);if(rightHeight == -1){return -1;}if(Math.abs(rightHeight-leftHeight)>1){return  -1;}else{return 1+Math.max(leftHeight,rightHeight);}

题目代码

class Solution {public boolean isBalanced(TreeNode root) {return getHeight(root) != -1;}int getHeight(TreeNode node){if(node == null){return 0;}int leftHeight = getHeight(node.left);if(leftHeight == -1){return -1;}int rightHeight = getHeight(node.right);if(rightHeight == -1){return -1;}if(Math.abs(rightHeight-leftHeight)>1){return  -1;}else{return 1+Math.max(leftHeight,rightHeight);}}
}

LeetCode T257 二叉树的所有路径

题目链接:257. 二叉树的所有路径 - 力扣(LeetCode)

题目思路

这里我们注意,使用到了回溯算法,其实递归和回溯是相辅相成的,就以上题的示例1为例,我们再记录了125这一条路线的时候还得回去记录13这一条路径,这就用到了回溯.这里千万不要把递归和回溯拆开,因为有一个递归就有一个回溯.

题目代码

class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> res = new ArrayList<>();if(root == null){return null;}List<Integer> path = new ArrayList<>();travsal(root,path,res);return res;}void travsal(TreeNode node,List<Integer> path,List<String> res){//前序path.add(node.val);if(node.left == null && node.right == null){StringBuilder sb = new StringBuilder();for(int i = 0;i<path.size()-1;i++){sb.append(path.get(i)).append("->");}sb.append(path.get(path.size()-1));res.add(sb.toString());}if(node.left != null){//一次递归一次回溯travsal(node.left,path,res);path.remove(path.size()-1);}if(node.right != null){travsal(node.right,path,res);path.remove(path.size()-1);}}
}

LeetCode T404 左叶子之和

题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

题目思路

这里我们注意之前我们只能判断叶子结点,而不能知道左叶子节点,这里我们就可以用过叶子结点的上一个节点知道是否为左叶子节点,这里我们仍然使用递归实现,这里就不需要额外创建新函数(仍然使用后序遍历)

1.函数返回值和参数

public int sumOfLeftLeaves(TreeNode root)


2.终止条件

无论是遇到空节点或者叶子节点都返回0,因为我们不知道该叶子结点是否为我们需要收集的节点

    if(root == null){return 0;}if(root.left == null && root.right == null){return 0;}

3.单层递归

        //后序int leftNum = sumOfLeftLeaves(root.left);int rightNum = sumOfLeftLeaves(root.right);int sum = 0;//中间处理过程if(root.left != null && root.left.left == null && root.left.right == null){sum = root.left.val;}sum = sum + leftNum + rightNum;return sum;

题目代码

class Solution {public int sumOfLeftLeaves(TreeNode root) {if(root == null){return 0;}if(root.left == null && root.right == null){return 0;}//后序int leftNum = sumOfLeftLeaves(root.left);int rightNum = sumOfLeftLeaves(root.right);int sum = 0;if(root.left != null && root.left.left == null && root.left.right == null){sum = root.left.val;}sum = sum+leftNum+rightNum;return sum;}}

相关文章:

代码随想录Day14 LeetCodeT110平衡二叉树 T257二叉树的所有路径 T404 左叶子之和

以下思路来自于: 代码随想录 (programmercarl.com) LeetCode T110 平衡二叉树 题目链接:110. 平衡二叉树 - 力扣&#xff08;LeetCode&#xff09; 题目思路 前面我们说过了,求二叉树的深度我们应该使用前序遍历,求二叉树的高度我们应该使用后序遍历,因为后序遍历可以将子树的…...

C语言自定义类型_枚举联合(3)

目录 枚举 什么是枚举类型&#xff1f; 枚举的声明 枚举的定义 枚举的优点 枚举的使用 联合&#xff08;共用体&#xff09; 什么是联合呢&#xff1f; 联合类型的定义 联合的特点 联合使用 联合大小的计算 联合的应用 今天接着我们来结束自定义类型。&#x1f19…...

asp.net网上销售系统VS开发mysql数据库web结构c#编程Microsoft Visual Studio计算机毕业设计

一、源码特点 asp.net 网上销售系统 是一套完善的web设计管理系统&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为vs2010&#xff0c;数据库为mysql&#xff0c;使用c#语言开发 aspnet 网上销售系统1 二、功能介绍 前台功能…...

【Windows】RPC调用过程实例详解

概述&#xff1a;windows 创建 RPC调用过程实例详解 参考文章&#xff1a;Remote procedure call (RPC)&#xff08;远程过程调用 (RPC)&#xff09; - Win32 apps | Microsoft Learn 文章目录 0x01、生成 UUID 和模版(IDL)文件0x02、添加 acf 文件0x03、编译 idl 文件0x04、客…...

动手学强化学习第2章多臂老虎机

2.1简介 多臂老虎机问题可以被看作简化版的强化学习问题。但是其只有动作和奖励没有状态信息&#xff0c;算是简化版的强化学习问题。 2.2问题介绍 2.2.1问题定义 在多臂老虎机(MAB)问题中&#xff0c;有一个有K根拉杆的老虎机&#xff0c;拉动每一根拉杆都对应一个关于奖励…...

钡铼BL124EC实现EtherCAT转Ethernet/IP的优势

钡铼技术的BL124EC是一款用于将EtherCAT从站转换为Ethernet/IP从站的网关设备。它是钡铼技术开发的高性能、可靠的工业自动化通信解决方案之一。 添加图片注释&#xff0c;不超过 140 字&#xff08;可选&#xff09; BL124EC网关可以应用于多种工业自动化场景&#xff0c;以下…...

使用IntelliJ Idea必备的插件!

趁手的工具让开发事半功倍&#xff0c;好用的IDEA插件让效率加倍。 今天给大家分享几个优秀的IDEA插件。 插件安装 首先得知道在IDEA哪安装插件&#xff1f; 点击File---->Settings---->找到Plugins标签&#xff0c;即可搜索想要的插件进行安装了。 现在来看下有哪些值…...

代码随想录算法训练营第23期day19| 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树

目录 一、&#xff08;leetcode 654&#xff09;最大二叉树 二、&#xff08;leetcode 617&#xff09;合并二叉树 三、&#xff08;leetcode 700&#xff09;二叉搜索树中的搜索 四、&#xff08;leetcode 98&#xff09;验证二叉搜索树 一、&#xff08;leetcode 654&…...

第四章 字符串part02 28. 实现strStr() 459. 重复的子字符串

第四章 字符串part02 28. 实现strStr() 459. 重复的子字符串 一、28. 实现strStr() 题目链接&#xff1a;https://leetcode.cn/problems/repeated-substring-pattern/ 题目介绍&#xff1a; 给定一个非空的字符串 s &#xff0c;检查是否可以通过由它的一个子串重复多次构成。…...

设计模式 - 状态模式

目录 一. 前言 二. 实现 一. 前言 状态模式&#xff08;State Pattern&#xff09;&#xff1a;它主要用来解决对象在多种状态转换时&#xff0c;需要对外输出不同的行为的问题。状态和行为是一一对应的&#xff0c;状态之间可以相互转换。当一个对象的内在状态改变时&#x…...

【vim 学习系列文章 9 -- .vim 脚本文件开发学习】

文章目录 .vimrc 介绍.vim 脚本文件开发 .vimrc 介绍 在Vim中&#xff0c;你可以将一系列的Vim命令和设置写入一个脚本文件中&#xff0c;并使用:source命令来运行它。这种脚本文件通常被称为vimrc文件&#xff0c;因为它的默认名称是.vimrc。通常&#xff0c;我们将这个文件放…...

NAT模式和桥接模式的区别

NAT模式和桥接模式的区别 NAT模式和桥接模式都是虚拟机网络配置的两种方式&#xff0c;主要区别在于虚拟机与外部网络交互的方式不同。 NAT&#xff08;Network Address Translation&#xff0c;网络地址转换&#xff09;模式&#xff1a;在这种模式下&#xff0c;虚拟机和宿主…...

应对出海安全合规挑战,兆珑科技为什么选择了亚马逊云科技?

在中国企业出海进程中&#xff0c;安全合规是企业面临的首要挑战。尤其是当企业业务涉及金融相关领域时&#xff0c;面临着最为严苛的安全合规要求。 深圳兆珑科技有限公司是一家全球化的物联网生态企业&#xff0c;其业务覆盖100多个国家和地区&#xff0c;在欧洲、南美、亚太…...

Allegro基本规则设置指导书之Spacing规则设置

进入规则设置界面 1.设置Line 到其他的之间规则: 2.设置Pins 到其他的之间规则: 3.设置Vias 到其他的之间规则:...

使用【Blob、Base64】两种方式显示【文本、图片、视频】 使用 video 组件播放视频

Blob 显示 Blob 对象的类型是由 MIME 类型&#xff08;Multipurpose Internet Mail Extensions&#xff09;来确定的。MIME 类型是一种标准&#xff0c;用于表示文档、图像、音频、视频等多媒体文件的类型。以下是一些常见的 Blob 对象类型&#xff1a; text/plain&#xff1…...

深度学习_1_基本语法

数据结构 代码&#xff1a; import torchx torch.arange(12)##产生长度为12的一维张量print(x)##X x.resize(3, 4)##被弃用##print(X)y torch.reshape(x, (3, 4))##修改向量为矩阵&#xff0c;一维变二维print(y)print(y.size())xx torch.zeros((2, 3, 4))##三维矩阵&…...

c#设计模式-行为型模式 之 中介者模式

&#x1f680;简介 又叫调停模式&#xff0c;定义一个中介角色来封装一系列对象之间的交互&#xff0c;使原有对象之间的耦合松散&#xff0c;且可以独立地改变它们之间的交互。 从下右图中可以看到&#xff0c;任何一个类的变 动&#xff0c;只会影响的类本身&#xff0c;以及…...

小程序uView2.X框架upload组件上传方法总结+避坑

呈现效果: 1.1单图片上传 1.2多图片上传 前言:相信很多人写小程序会用到uView框架,总体感觉还算OK吧,只能这么说,肯定也会遇到图片视频上传,如果用到这个upload组件相信你,肯定遇到各种各样的问题,这是我个人总结的单图片和多图片上传方法. uView2.X框架:uView 2.0 - 全面兼容…...

人脸检测及追踪回顾

轻量级人脸检测 代码地址 人脸追踪 代码地址 MNN框架部署文档 文档地址...

虚拟环境和包

目录 12. 虚拟环境和包 12.1. 简介 12.2. 创建虚拟环境 12.3. 使用 pip 管理包 12. 虚拟环境和包 12.1. 简介 Python 应用程序经常会使用一些不属于标准库的包和模块。应用程序有时候需要某个特定版本的库&#xff0c;因为它需要一个特定的 bug 已得到修复的库或者它是使用…...

App无辜躺枪?手把手教你搞定腾讯手机管家误报导致的应用商店下架

当合规应用遭遇误报下架&#xff1a;开发者系统性应对指南运动健康类应用被标记为金融诈骗软件&#xff1f;社交工具因"病毒风险"被各大商店紧急下架&#xff1f;这类看似荒谬的误报事件&#xff0c;正在成为中小开发团队的"无妄之灾"。某知名运动App开发团…...

从分立逻辑到单片机:基于ATmega8的MIDI通道分析仪设计与实现

1. 项目概述&#xff1a;从分立逻辑到单片机的MIDI通道分析仪进化史二十年前&#xff0c;当我在《Elektor》杂志上发表第一版MIDI通道分析仪时&#xff0c;整个数字音乐世界还处于一个相当“硬核”的阶段。那个版本的设计&#xff0c;用今天的话来说&#xff0c;简直就是一场“…...

雪球网md5__1038参数逆向解析与Node.js复现

1. 这不是“破解”&#xff0c;而是对前端加密逻辑的常规逆向还原你打开雪球网任意一只股票详情页&#xff0c;F12 打开开发者工具&#xff0c;切到 Network 面板&#xff0c;刷新页面——很快就能在 XHR 请求里捕获到类似这样的接口&#xff1a;https://xueqiu.com/stock/cube…...

Qri高级功能:如何使用JSON Schema验证和描述数据集结构

Qri高级功能&#xff1a;如何使用JSON Schema验证和描述数据集结构 【免费下载链接】qri youre invited to a data party! 项目地址: https://gitcode.com/gh_mirrors/qr/qri Qri是一个强大的开源数据协作工具&#xff0c;它提供了丰富的功能来帮助用户管理、共享和验证…...

BiliRoamingX:彻底解决B站体验限制的完整增强方案

BiliRoamingX&#xff1a;彻底解决B站体验限制的完整增强方案 【免费下载链接】BiliRoamingX-integrations BiliRoamingX integrations and patches powered by ReVanced. 项目地址: https://gitcode.com/gh_mirrors/bi/BiliRoamingX-integrations 你是否曾为B站的内容区…...

TVA注意力层INT8量化配置技巧

重磅预告&#xff1a;本专栏将独家连载系列丛书《智能体视觉技术与应用》部分精华内容&#xff0c;该书是世界首套系统阐述“因式智能体”视觉理论与实践的专著&#xff0c;特邀美国 TypeOne 公司首席科学家、斯坦福大学博士 Bohan 担任技术顾问。Bohan先生师从美国三院院士、“…...

Codex使用API Key授权无法使用插件?

小伙伴们&#xff0c;大家好&#xff0c;我是小溪&#xff0c;见字如面。对于没有ChatGPT账号的小伙伴来说&#xff0c;虽然可以通过API Key授权的方式使用Codex桌面端&#xff0c;但是会有一些限制。比如无法使用插件功能&#xff0c;无法使用Codex移动端进行远程控制等。为了…...

基于SMD与贝壳的微型音频装置:从电路设计到嵌入式开发的完整实践

1. 项目概述&#xff1a;一个藏在贝壳里的声音世界你小时候有没有捡起一个海螺壳&#xff0c;把它贴在耳边&#xff0c;然后听到里面传来“呜呜”的海风声&#xff1f;那个瞬间&#xff0c;仿佛整个海洋都被装进了小小的贝壳里。今天这个项目&#xff0c;就是把那个童年的魔法&…...

深度解析:JetBrains IDE试用期重置机制的技术实现

深度解析&#xff1a;JetBrains IDE试用期重置机制的技术实现 【免费下载链接】ide-eval-resetter 项目地址: https://gitcode.com/gh_mirrors/id/ide-eval-resetter 在软件开发工作流中&#xff0c;JetBrains IDE试用期管理是一个常见的技术挑战&#xff0c;尤其是在多…...

模拟电路实现自主循线机器人:无MCU的硬件逻辑设计

1. 项目概述&#xff1a;用最纯粹的模拟电路&#xff0c;造一台会“思考”的机器人每次看到那些在赛道上灵巧穿梭的循线小车&#xff0c;你是不是也手痒&#xff0c;想自己动手做一个&#xff1f;但一听到“单片机”、“编程”、“Arduino”这些词&#xff0c;又觉得门槛太高&a…...