【leetcode面试经典150题】74. 填充每个节点的下一个右侧节点指针 II(C++)

【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主,题解使用C++语言。(若有使用其他语言的同学也可了解题解思路,本质上语法内容一致)

【题目描述】

给定一个二叉树:

struct Node {int val;Node *left;Node *right;Node *next;
}

填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL 。

初始状态下,所有 next 指针都被设置为 NULL 。

【示例一】

输入:root = [1,2,3,4,5,null,7]
输出:[1,#,2,3,#,4,5,7,#]
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化输出按层序遍历顺序(由 next 指针连接),'#' 表示每层的末尾。

【示例二】

输入:root = []
输出:[]

【提示及数据范围】

  • 树中的节点数在范围 [0, 6000] 内
  • -100 <= Node.val <= 100

【代码】

// 方法一:层次遍历class Solution {
public:Node* connect(Node* root) {if (!root) {return nullptr;}queue<Node*> q;q.push(root);while (!q.empty()) {int n = q.size();Node *last = nullptr;for (int i = 1; i <= n; ++i) {Node *f = q.front();q.pop();if (f->left) {q.push(f->left);}if (f->right) {q.push(f->right);}if (i != 1) {last->next = f;}last = f;}}return root;}
};// 方法二:使用已建立的 next 指针class Solution {
public:void handle(Node* &last, Node* &p, Node* &nextStart) {if (last) {last->next = p;} if (!nextStart) {nextStart = p;}last = p;}Node* connect(Node* root) {if (!root) {return nullptr;}Node *start = root;while (start) {Node *last = nullptr, *nextStart = nullptr;for (Node *p = start; p != nullptr; p = p->next) {if (p->left) {handle(last, p->left, nextStart);}if (p->right) {handle(last, p->right, nextStart);}}start = nextStart;}return root;}
};

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

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

相关文章

powerJob升级为nacos版本

power版本 4.3.9 powerjob-server/powerjob-server-starter添加pom.xml <!-- https://mvnrepository.com/artifact/com.alibaba.cloud/spring-cloud-starter-alibaba-nacos-discovery --> <dependency><groupId>com.alibaba.cloud</groupId><art…

【C#】Stopwatch计时器

使用Stopwatch检查C#中代码块的执行时间&#xff0c;比如歌曲&#xff0c;图片的下载时间问题 首先&#xff0c;我们可看到Stopwatch 类内部的函数。 根据需求&#xff0c;我们具体可使用到 Start() 开始计时&#xff0c;Stop() 停止计时等 //创建 Stopwatch 实例 Stopwatch …

WEB攻防-PHP特性-函数缺陷对比

目录 和 MD5函数 intval ​strpos in_array preg_match str_replace 和 使用 时&#xff0c;如果两个比较的操作数类型不同&#xff0c;PHP 会尝试将它们转换为相同的类型&#xff0c;然后再进行比较。 使用 进行比较时&#xff0c;不仅比较值&#xff0c;还比较变量…

通配符HTTPS安全证书

众多类型的SSL证书&#xff0c;要说适用或者说省钱肯定是通配符了&#xff0c;因为谁都想一本SSL证书包括了整条域名&#xff0c;而且也不用一条一条单独管理。 通配符HTTPS安全证书&#xff0c;其实就是通配符SSL证书&#xff0c;SSL证书主流CA的参数都一样&#xff0c;通配符…

【学习笔记之vue】vue项目放在springboot项目里后,刷新页面会显示whitelabel error page

vue项目放在springboot项目里后&#xff0c;刷新页面会显示whitelabel error page。 解决方案: 当你在Spring Boot项目中嵌入Vue项目&#xff0c;并且刷新页面时遇到了“Whitelabel Error Page”&#xff0c;这通常意味着Spring Boot后端没有正确地处理前端路由的请求。Vue.j…

GitOps 和 DevOps 有什么区别?

GitLab 是一个全球知名的一体化 DevOps 平台&#xff0c;很多人都通过私有化部署 GitLab 来进行源代码托管。极狐GitLab &#xff1a;https://gitlab.cn/install?channelcontent&utm_sourcecsdn 是 GitLab 在中国的发行版&#xff0c;专门为中国程序员服务。可以一键式部署…

nginx反向代理.NetCore开发的基于WebApi创建的gRPC服务

一、本文中使用的工具: Vs2022使用.NET 8.0开发基于ASP.NET Core WebApi的gRPC服务; Nginx:1.25.5,下载地址:http://nginx.org/en/download.html 二、gRPC介绍: 由 google 开发,是一款语言中立、平台中立、开源的远程过程调用(RPC)系统。在vs2022中可以直接创建gRP…

C语言趣味代码(二)

1.珠玑妙算 1.1 介绍 《珠玑妙算》(Mastermind)是英国Invicta公司于1973年开始销售的一款益智游戏&#xff0c;据说迄今为止已经在全世界销售了5000万套。《珠玑妙算》于1974年获奖后&#xff0c;在1975年传入美国&#xff0c;1976年leslieH.Autl博士甚至还出版了一本名为The…

leetcode多个测试用例之间相互影响导致提交失败

背景 在做一道easy题&#xff0c;二叉树的中序遍历&#xff0c;我提交的代码如下 from typing import (Optional,List )# Definition for a binary tree node. class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right right…

前端框架EXT.NET Dotnet 3.5开发的实验室信息管理系统(LIMS)成品源码 B/S架构

前端框架EXT.NET Dotnet 3.5开发的实验室信息管理系统&#xff08;LIMS&#xff09;成品源码 B/S架构 LIMS实验室管理系统 发展历史 实验室信息管理系统(LIMS)&#xff0c;就是指通过计算机网络技术对实验的各种信息进行管理的计算机软、硬件系统。也就是将计算机网络技术与现…

使用LVGL提升交互效率:基于启明智显Model3A方案的7寸智能屏用户界面(UI)设计介绍

项目概述&#xff1a; 【启明智显】&#xff0c;作为一家专注于HMI和AIoT解决方案的公司&#xff0c;我们致力于为用户提供创新、可靠且高效的产品和解决方案。近日我们推出了高性能及高性价比的HMI芯片——Model3A。芯片搭载了强大的2D图形加速引擎&#xff0c;能够提供高达7…

这个合租室友真的没有一点公德心,还好他搬走了

这个合租室友真的没有一点公德心&#xff0c;还好他搬走了 这个出租屋有四个房间。 有三个卧室&#xff0c;和一个隔断。 我住三个卧室中的一个。下图中右边那个就是我住的。 2023年下半年&#xff0c;左边那个屋子来了一个新租户小白。 在住的过程中&#xff0c;隔断间的租…

C语言求 MD5 值

MD5值常被用于验证数据的完整性&#xff0c;嵌入式开发时经常用到。md5sum命令可以求MD5码&#xff0c;下面介绍如何用C语言实现MD5功能。 一、求字符串MD5值 1、md5sum命令 $ echo -n "12345678" | md5sum //获取"12345678"字符串的md5值 结果&…

STM32单片机C语言模块化编程实战:LED控制详解与示例

一、开发环境 硬件&#xff1a;正点原子探索者 V3 STM32F407 开发板 单片机&#xff1a;STM32F407ZGT6 Keil版本&#xff1a;5.32 STM32CubeMX版本&#xff1a;6.9.2 STM32Cube MCU Packges版本&#xff1a;STM32F4 V1.27.1 之前介绍了很多关于点灯的方法&#xff0c;比如…

机器学习——过拟合

一、过拟合得表现 模型在训练过程中&#xff0c;除了会出现过拟合现象&#xff0c;还有可能出现欠拟合的情况。相比而言&#xff0c;后者通常发生在建模前期&#xff0c;只要做好特征工程一般可以解决模型欠拟合问题。下图描述了模型在训练数据集上的三种情况&#xff1a; 其…

opencv_5_图像像素的算术操作

方法1&#xff1a;调用库函数 void ColorInvert::mat_operator(Mat& image) { Mat dst; Mat m Mat::zeros(image.size(), image.type()); m Scalar(2, 2, 2); multiply(image, m, dst); m1 Scalar(50,50, 50); //divide(image, m, dst); //add(im…

基于vue+node+mysql的视频校对系统

一、登录注册&#xff1a;包括登录&#xff0c;注册&#xff0c;忘记密码&#xff0c;验证码等常用点。 二、用户管理&#xff1a;包括用户的增删改查 三、权限管理&#xff08;请增加这个权限&#xff1a;任务分配——只有管理者才能发布和删除任务&#xff1b;管理员设置。 四…

图论基础知识 深度优先(Depth First Search, 简称DFS),广度优先(Breathe First Search, 简称DFS)

图论基础知识 学习记录自代码随想录 dfs 与 bfs 区别 dfs是沿着一个方向去搜&#xff0c;不到黄河不回头&#xff0c;直到搜不下去了&#xff0c;再换方向&#xff08;换方向的过程就涉及到了回溯&#xff09;。 bfs是先把本节点所连接的所有节点遍历一遍&#xff0c;走到下…

每日一题:跳跃游戏II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说&#xff0c;如果你在 nums[i] 处&#xff0c;你可以跳转到任意 nums[i j] 处: 0 < j < nums[i] i j < n 返回到达 nums[n - 1] 的最…

react —— useState 深入

基础用法 useState Hook 提供了这两个功能&#xff1a; State 变量 在第一次重新渲染期间&#xff0c;这将具有作为参数传递的值State setter 函数 set 函数将允许将状态的值更新为不同的值&#xff0c;如果 set 函数中提供的值不同&#xff0c;则将触发重新渲染。 注意&…