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

server/2024/11/15 8:33:29/

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.ppmy.cn/server/23523.html

相关文章

常用的网站和软件

编程社区 Stack Overflow - 全球最大的编程问题解答社区&#xff0c;涵盖各种编程语言和技术。网址&#xff1a;https://stackoverflow.comCSDN - 主要面向中国开发者的技术社区&#xff0c;提供技术文章、论坛帖子和博客。网址&#xff1a;https://www.csdn.net 开发软件 J…

Excel文件解析--超大Excel文件读写

使用POI写入 当我们想在Excel文件中写入100w条数据时&#xff0c;我们用普通的XSSFWorkbook对象写入时会发现&#xff0c;只有在将100w条数据全部加载入内存后才会用write()方法统一写入&#xff0c;这样效率很低&#xff0c;所以我们引入了SXSSFWorkbook进行超大Excel文件的读…

python爬虫6

1 简介 BeautifulSoup 是一个用于解析HTML和XML文档的Python库。它提供了一种灵活和便捷的方式来导航、搜索和修改解析树。BeautifulSoup简化了网络爬虫的工作&#xff0c;使得开发者可以轻松地解析网页内容&#xff0c;提取所需的数据。 2 初体验 使用BeautifulSoup的第一步…

初探 JUC 并发编程:Java 并发包中并发 List 源码剖析

最近在阅读 《Java 并发编程之美》这本书&#xff0c;感觉学到了很多东西&#xff1b;所以我决定将从事书中学到的思想和一些经典的案例整理成博客的形式与大家分享和交流&#xff0c;如果对大家有帮助别忘了留下点赞和关注捏。 第五部分&#xff1a;Java 并发包中并发 List 源…

QT彻底解决中文乱码问题(代码、普通文件、ini文件、路径)

文章目录 代码中包含中文普通文件包含中文ini文件包含中文路径包含中文网络请求中包含中文由于QT程序是跨平台的且中文在不同平台下的编码方式不同,为了让QT程序更好的处理中文,我们需要针对中文进行单独的处理,这里介绍一下QT程序在不同场景下如何处理显示中文。 代码中包含…

常见的工业路由器访问问题

A&#xff1a;工业路由器已经设置了pptp怎么访问路由下面的电脑 1. 确认PPTP VPN设置&#xff1a;首先&#xff0c;确保PPTP VPN服务器在工业路由器上已正确设置&#xff0c;并且处于活动状态。这包括确保VPN服务器的IP地址、端口、用户名和密码等设置正确无误。 2. 连接到VP…

GN 编译系统简介

GN 编译系统简介 GN&#xff08;Generate Ninja&#xff09;是由 Google 开发的一个元构建系统&#xff0c;它的主要职责是生成 Ninja 构建文件&#xff0c;进而驱动 Ninja 构建工具完成实际的编译、链接等工作。GN 使用一种自定义的声明式语言来编写构建配置文件&#xff0c;…

AI手机,走入小径分岔的花园

博尔赫斯在他的成名作《小径分岔的花园》里&#xff0c;描述了一种奇妙的世界观&#xff1a;一个可能性被选择之后&#xff0c;出现了许多不同的后世&#xff0c;许多不同的时间。 在现实世界中&#xff0c;选择不会如此神奇。但站在岔路口的抉择&#xff0c;也一定会带来结果的…