【LeetCode75】第三十七题 二叉树中的最长交错路径

目录

 

题目:

示例:

分析:

代码:


题目:

示例:

分析:

给我们一棵二叉树,问我们在这棵树里能找到的最长交错路径。最长交错路径就是在二叉树里一左一右一左一右这样走,最长能走的路径长度是多少。

这种二叉树类的题目我们是少不了递归遍历,这次递归我们需要携带参数去递归,就是记录我上一次是左拐还是右拐,然后每次遍历到新的节点我们都需要重新来以此节点作为路径的起始节点来递归。

例如我上一次在二叉树里是右拐,那么接下来我的递归,如果是左走的话,我就把记录路径长度的参数+1然后再次递归,并且还需要多一层递归,那就是路径长度从0开始重新计算的一层递归。

具体可以参考下面的代码。

代码:

class Solution {
public:
    int res=0;
    void digui(TreeNode* root,int flag,int temp){
        if(root==nullptr){
            res=max(res,temp);
            return;
        }
        //使用flag来记录上一个是往左移还是往右移
        if(flag==0){    //flag==0则表示上一次是往左移,因此接下来如果是右移的话就把记录的路径长度+1
            digui(root->right,1,temp+1);
            digui(root->left,0,0);  //左移则表示从0开始左右交错,路径长度置0.
        }else{
            digui(root->left,0,temp+1);
            digui(root->right,1,0);
        }
    }
    int longestZigZag(TreeNode* root) {
        if(root==nullptr) return 0;
        digui(root->left,0,0);
        digui(root->right,1,0);
        return res;
    }
};

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

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

相关文章

Windows下搭建Tomcat HTTP服务,发布外网远程访问

文章目录 前言1.本地Tomcat网页搭建1.1 Tomcat安装1.2 配置环境变量1.3 环境配置1.4 Tomcat运行测试1.5 Cpolar安装和注册 2.本地网页发布2.1.Cpolar云端设置2.2 Cpolar本地设置 3.公网访问测试4.结语 前言 Tomcat作为一个轻量级的服务器,不仅名字很有趣&#xff0…

港联证券|燃气板块午后走高,美能能源涨停,水发燃气大幅拉升

燃气板块21日午后快速拉升,到发稿,美能动力涨停,水发燃气涨超7%,蓝天燃气涨超5%,贵州燃气涨逾4%。 消息面上,受澳大利亚LNG工厂罢工忧虑影响,欧洲基准天然气价格一度大涨18%。 有报导称&#x…

Zenity 简介

什么使 Zenity Zenity 是一个开源的命令行工具,它提供了一种简单的方式来创建图形化的用户界面(GUI)对话框,以与用户进行交互。它基于 GTK 库,可以在 Linux 和其他 UNIX-like 系统上使用。 Zenity 可以通过命令行或脚…

使用windeployqt和InstallShield打包发布Qt软件的流程

前言 Qt编译之后需要打包发布,并且发布给用户后需要增加一个安装软件,通过安装软件可以实现Qt软件的安装;用于安装软件的软件有很多,这里主要介绍InstallShield使用的流程; 使用windeployqt打包Qt编译后的程序 Qt程序…

Linux操作系统--文件与目录结构

我们初步认识了Linux操作系统,下面我们进一步看看linux的文件与目录结构。 1.文件系统和挂载点 (1).当前的操作系统中查看文件系统 位置 > 计算机 这样你就可以看见当前操作系统中的所有目录和文件。如下所示: (2).挂载点 挂载点实际上就是linux中的磁盘文件系统的入口…

Unittest 笔记:unittest拓展生成HTM报告发送邮件

HTMLTestRunner 是一个unitest拓展可以生成HTML 报告 下载地址:GitHub: https://github.com/defnnig/HTMLTestRunner HTMLTestRunner是一个独立的py文件,可以放在Lib 作为第三方模块使用或者作为项目的一部分。 方式1: 验证是否安装成功&…

STM32f103入门(2)流水灯蜂鸣器

流水灯 /* #define GPIO_Pin_0 ((uint16_t)0x0001) /*!< Pin 0 selected */ #define GPIO_Pin_1 ((uint16_t)0x0002) /*!< Pin 1 selected */ #define GPIO_Pin_2 ((uint16_t)0x0004) /*!< Pin 2 selected */ #de…

无涯教程-机器学习 - Jupyter Notebook函数

Jupyter笔记本基本上为开发基于Python的数据科学应用程序提供了一个交互式计算环境。它们以前称为ipython笔记本。以下是Jupyter笔记本的一些功能,使其成为Python ML生态系统的最佳组件之一- Jupyter笔记本可以逐步排列代码,图像,文本,输出等内容,从而逐步说明分析过程。 它有…

带你启用window10专业版系统自带的远程桌面

启用window10专业版系统自带的远程桌面 文章目录 启用window10专业版系统自带的远程桌面前言1.找到远程桌面的开关2. 找到“应用”项目3. 打开需要远程操作的电脑远程桌面功能 总结 前言 Windows操作系统作为应用最广泛的个人电脑操作系统&#xff0c;在我们身边几乎随处可见。…

JavaWeb学习-Day10

SpringBootWeb案例 准备工作 开发流程&#xff1a; 开发接口步骤&#xff1a; 删除部门&#xff1a; 新增部门&#xff1a; 简化代码&#xff1a; limit:分页展示&#xff0c;公式&#xff1a;&#xff08;页数-1&#xff09;*页面总数&#xff0c;页面总数 目前出现的问题&am…

【Eclipse】汉化简体中文教程(官方汉化包,IDE自带软件安装功能),图文详情

目录 0.环境 1.步骤 1&#xff09;查看eclipse的版本 2&#xff09;在官网找语言包&#xff0c;并复制链接 3&#xff09;将链接复制到eclipse中 4&#xff09;汉化完成 0.环境 windows11&#xff0c;64位&#xff1b; eclipse 2021-6版本 1.步骤 思路&#xff1a;在官网找…

MVC OR DDD

MVC OR DDD 说明&#xff1a;这篇是标题党&#xff0c;不包含相关概念说明 前段时间跟随师兄学习了解了DDD领域驱动模型&#xff0c;觉得这个思想更好&#xff0c;进行下面解析和学习方面的思考和实践&#xff0c;觉得很好&#xff0c;耐心读下去。希望对您有所帮助。 首先&am…

Nginx详解 一:编译安装Nginx和Nginx模块

文章目录 1.HTTP 和 Nginx1.1 Socket套接字1.2 HTTP工作机制1.2.1一次http事务1.2.2 资源类型1.2.3提高HTTP连接性能 2. I/O模型2.1 I/O模型相关概念2.2 网络I/O模型2.2.1 **阻塞型** **I/O** 模型&#xff08;blocking IO&#xff09;2.2.2 **非阻塞型** **I/O** **模型** **(…

开始MySQL之路—— DDL语法、DML语法、DQL语法基本操作详解

DDL语法 DDL&#xff08;Data Definition Language&#xff09; 数据定义语言&#xff0c;该语言部分包括以下内容。 对数据库的常用操作 对表结构的常用操作 修改表结构 对数据库的常用操作 1: 查看当前所有的数据库 show databases; 2&#xff1a;创建数据库 create dat…

回归预测 | MATLAB实现SSA-ELM麻雀搜索算法优化极限学习机多输入单输出回归预测(多指标,多图)

回归预测 | MATLAB实现SSA-ELM麻雀搜索算法优化极限学习机多输入单输出回归预测&#xff08;多指标&#xff0c;多图&#xff09; 目录 回归预测 | MATLAB实现SSA-ELM麻雀搜索算法优化极限学习机多输入单输出回归预测&#xff08;多指标&#xff0c;多图&#xff09;效果一览基…

2000-2021年上市公司绿色投资环保投资与营业收入之比数据(原始数据+计算代码+计算结果)

2000-2021年上市公司绿色投资环保投资与营业收入之比数据&#xff08;原始数据计算代码计算结果&#xff09; 1、时间&#xff1a;2000-2021年 2、来源&#xff1a;上市公司年报 3、指标&#xff1a;证券代码、企业名称、年份、管理费用环保投资、管理费用环保投资/营业收入…

第 360 场 LeetCode 周赛题解

A 距离原点最远的点 串中的 “_” 处要么都向左走要么都向右走 class Solution { public:int furthestDistanceFromOrigin(string moves) {int t 0;for (auto x: moves)if (x ! R)t--;elset;int res abs(t);t 0;for (auto x: moves)if (x ! L)t;elset--;res max(res, abs(t…

0821|C++day1 初步认识C++

一、思维导图 二、知识点回顾 【1】QT软件的使用 1&#xff09;创建文件 创建文件时&#xff0c;文件的路径一定是全英文 2&#xff09;修改编码 工具--->选项--->行为--->默认编码&#xff1a;system 【2】C和C的区别 C又叫C plus plus&#xff0c;C是对C的扩充&…

基于React实现日历组件详细教程

前言 日历组件是常见的日期时间相关的组件&#xff0c;围绕日历组件设计师做出过各种尝试&#xff0c;展示的形式也是五花八门。但是对于前端开发者来讲&#xff0c;主要我们能够掌握核心思路&#xff0c;不管多么奇葩的设计我们都能够把它做出来。 本文将详细分析如何渲染一…

WPF基础入门-Class2-样式

WPF基础入门 Class2&#xff1a;样式 1、内联样式&#xff1a;优先度最高 <Grid><StackPanel><!--内联样式优先度高--><Button Background"Red" Height"10" Width"100"FontSize"20"Content"SB">…