(二叉树) 116. 填充每个节点的下一个右侧节点指针 ——【Leetcode每日一题】

news/2024/2/29 3:48:23

❓ 116. 填充每个节点的下一个右侧节点指针

难度:中等

给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:

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

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

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

示例 1:

在这里插入图片描述

输入:root = [1,2,3,4,5,6,7]
输出:[1,#,2,3,#,4,5,6,7,#]
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化的输出按层序遍历排列,同一层节点由 next 指针连接,‘#’ 标志着每一层的结束。

示例 2:

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

提示

  • 树中节点的数量在 [ 0 , 2 12 − 1 ] [0, 2^{12} - 1] [0,2121] 范围内
  • − 1000 < = n o d e . v a l < = 1000 -1000 <= node.val <= 1000 1000<=node.val<=1000

进阶

  • 你只能使用常量级额外空间。
  • 使用递归解题也符合要求,本题中递归程序占用的栈空间不算做额外的空间复杂度。

💡思路:前序遍历(递归)

假如当前操作的节点是 cur

  • 最关键的点是可以通过上一层递归 搭出来的线,进行本次搭线。

在这里插入图片描述

🍁代码:(Java、C++)

Java

/*
// Definition for a Node.
class Node {public int val;public Node left;public Node right;public Node next;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, Node _left, Node _right, Node _next) {val = _val;left = _left;right = _right;next = _next;}
};
*/class Solution {private void traversal(Node cur){if(cur == null) return;if(cur.left != null) cur.left.next = cur.right;if(cur.right != null) {if(cur.next != null) cur.right.next = cur.next.left;else cur.right.next = null;}traversal(cur.left);traversal(cur.right);}public Node connect(Node root) {traversal(root);return root;}
}

C++

/*
// Definition for a Node.
class Node {
public:int val;Node* left;Node* right;Node* next;Node() : val(0), left(NULL), right(NULL), next(NULL) {}Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}Node(int _val, Node* _left, Node* _right, Node* _next): val(_val), left(_left), right(_right), next(_next) {}
};
*/class Solution {
private:void traversal(Node* cur){if(cur == nullptr) return;if(cur->left != nullptr) cur->left->next = cur->right;if(cur->right != nullptr){if(cur->next != nullptr) cur->right->next = cur->next->left;else cur->right->next = nullptr;}traversal(cur->left);traversal(cur->right);}
public:Node* connect(Node* root) {traversal(root);return root;}
};

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),每个节点只访问一次。
  • 空间复杂度 O ( 1 ) O(1) O(1),不需要存储额外的节点。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/516286.html

相关文章

结构型设计模式07-享元模式

&#x1f9d1;‍&#x1f4bb;作者&#xff1a;猫十二懿 ❤️‍&#x1f525;账号&#xff1a;CSDN 、掘金 、个人博客 、Github &#x1f389;公众号&#xff1a;猫十二懿 享元模式 1、享元模式介绍 享元模式是一种结构型设计模式&#xff0c;旨在**通过共享对象来减少内存使…

ATFX:黑海运粮遭俄暂停,小麦期货开盘跳涨

俄乌冲突一直是国际能源和粮食供应的最大不确定性因素。今年7月22日&#xff0c;俄罗斯、乌克兰、土耳其和联合国代表在土耳其首都伊斯坦布尔签署有关乌克兰农产品在黑海港口外运的相关协议。 ▲ATFX供图 自此以后&#xff0c;关于国际粮食危机&#xff08;准确说是欧洲粮食危…

【OCM第19期开班第2场】第19期11g OCM培训第2场将于今晚20点在腾讯课堂免费上课...

注意&#xff1a;据最新内部消息&#xff0c;11g的OCM最晚考试时间延迟到2020年4月底&#xff0c;所以&#xff0c;想考11g OCM的同学可以抓紧时间报名。 Oracle 11g ocm第19期将于今天晚上20点在腾讯课堂免费上课&#xff0c;第2场考试免费培训&#xff0c;包过&#xff0c;题…

【麦课】1~OEL的下载

OEL的下载 视频观看地址&#xff1a; https://v.qq.com/x/page/u0717e7s2al.html https://edelivery.oracle.com 注意的是&#xff1a;第一次下载安装的时候需要首先安装installer.exe软件&#xff0c;然后再下载即可。 小麦苗课程 小麦苗课堂开课啦&#xff0c;如下是现有的…

Oracle 11g RAC安装--基于openfiler存储+多路径+udev方式

Oracle 11g RAC安装--基于openfiler存储多路径udev方式 RAC安装部分视频&#xff08;温馨提示&#xff1a;播放地址复制到浏览器可看超清版或下载原视频文件&#xff0c;云盘下载地址&#xff1a;https://share.weiyun.com/5iJLFCK&#xff09;&#xff0c;包括免费视频和讲课…

中国脱粒机行业市场供需与战略研究报告

出版商&#xff1a;贝哲斯咨询 获取报告样本&#xff1a; 企业竞争态势 脱粒机市场报告涉及的主要国际市场参与者有Mahindra & Mahindra、John Deere、Kubota、Deluxe Agro Industries、AGCO、Bharat Industries、Iseki & Co、ALMACO、Alvan Blanch、Wuhan Acme Agro…

每日一练-牛奶交易

牛奶交易 &#x1f340;题目描述&#x1f33f;解题思路&#x1f338;Python源码&#x1f4e7;Summary &#x1f4c6;Date: 2023年1月18日 &#x1f3ac;Author: 小 y 同 学 &#x1f4c3;Classify: 蓝桥杯每日一练 &#x1f516;Language: Python &#x1f340;题目描述 题意  …

如果给定世界价格是1单位计算机交换22,国际贸易习题

3.运用要素禀赋理论&#xff0c;分析我国的出口商品结构。 4.请解释发展中国家的出口贫困增长。 5. ★下表列出了加拿大和中国生产一单位计算机和一单位小麦所需的劳动时间。假定生产计算机和小麦都只用劳动&#xff0c;加拿大的总劳动为600 小时&#xff0c;中国总劳动为800 小…

如果给定世界价格是1单位计算机交换22,可以帮帮我吗?我有几个题目不会做,有劳各位了。...

该楼层疑似违规已被系统折叠 隐藏此楼查看此楼 1下表例出了加拿大和中国生产1单位计算机和1单位小麦所需的劳动时间。假定生产计算机和小麦所需要的劳动时间。假定生产计算机和小麦都只用劳动&#xff0c;加拿大的总劳动为600小时&#xff0c;中国的总劳动为800小时。 计算机 …

开瑞k60价格多少_2020最新白酒测评:茅台K60白酒怎么样

注&#xff1a;本文转载自网络&#xff0c;不代表本平台立场&#xff0c;仅供读者参考&#xff0c;著作权属归原创者所有。我们分享此文出于传播更多资讯之目的。如有侵权&#xff0c;请在后台留言联系我们进行删除&#xff0c;谢谢&#xff01; 大家都知道&#xff0c;现如今…

“抗旱保收”消除减产忧虑,小麦期价冲高回落

“抗旱保收”消除减产忧虑&#xff0c;小麦期价冲高回落 上证报记者钱晓涵 走强多日的小麦期货昨日放缓了上攻的步伐。郑州商品交易所优质强筋小麦昨天冲高回落&#xff0c;主力合约0905收报2055元/吨&#xff0c;与上一交易日结算价持平&#xff1b;另一主力合约0909收报2179元…

[渝粤教育] 中国地质大学 经济学原理 复习题 (2)

《经济学原理》模拟题 一.单选题 1.&#xfeff;假如厂商的收益不足以弥补可变成本为了把损失减少到最低程度他应该(). A.减少产量 B.增加产量 C.停止生产 2.&#xfeff;紧缩性货币政策的运用会导致(). A.增加商业银行存入中央银行的存款 B.减少商业银行的贷款总额 C.提高利息…

如果给定世界价格是1单位计算机交换,克鲁格曼《国际经济学》计算题及答案...

比较优势,有效保护率 1. 在古典贸易模型中&#xff0c;假设A国有120名劳动力&#xff0c;B国有50名劳动力&#xff0c;如果生产棉花的话&#xff0c;A国的人均产量是2吨&#xff0c;B国也是2吨&#xff1b;要是生产大米的话&#xff0c;A国的人均产量是10吨&#xff0c;B国则是…

《一课经济学》六、政府价格管制

上期我们说了价值体系是如何运作的&#xff0c;本期节目我们来聊一聊政府针对商品价格制定政策的问题。 政府限制价格过低 我们经常能听到这样的声音&#xff0c;说某某物品的价格太低&#xff0c;厂商已经在亏本经营了&#xff0c;如果政府不限价&#xff0c;厂商就会纷纷倒闭…

假如贸易条件为1单位计算机换22单位小麦,请哪位强人帮我解答下有关国际贸易的一道题...

请哪位强人帮我解答下有关国际贸易的一道题 來源:互聯網 2009-12-08 10:44:04 評論 分類: 商業/理財 >> 貿易 問題描述: 下表列示了法国与的国生产每单位的计算机与小麦所需要的劳动天数 计算机 小麦 法 100 4 德 60 3 1、计算自己自足经济下的价格水平 2、哪一个国家在…

视频流车辆计数与轨迹跟踪、小麦检测等实战项目上手演练

企业管理者说&#xff0c; 我想尝试在业务场景中应用AI&#xff0c;但没有资深算法工程师&#xff0c;怎么办&#xff1f; 业务场景复杂&#xff0c;数据积累不足、质量参差不齐&#xff0c;如何快速优化&#xff1f; 各大厂商的AI芯片和硬件层出不穷&#xff0c;性能、功耗、价…

Machine Learning机器学习术语记录

目录 标签 label 特性 features 样本 模型 model 回归与分类 标签 label 标签是指我们要预测的内容&#xff0c;即简单线性回归中的 y 变量。标签可以是小麦的未来价格、图片中显示的动物类型、音频剪辑的含义&#xff0c;也可以是其他任何信息。 特性 features 特征是…

基于pyqt5、mysql、yolov7、chatgpt的小麦病害检测系统v1.0

基于pyqt5、mysql、yolov7、chatgpt的小麦病害检测系统设计与实现 一、界面设计1.1安装pyqt51.2创建用户子窗体1.3创建管理员主窗体1.4创建管理员子窗体1.5创建系统登陆界面 二、环境搭建2.1pyqt5工具配置2.2mysql5.7安装 三、编程实现3.1初始化数据库3.2创建用户数据库sdk文件…

2022年全球市场脱脂小麦胚芽粉总体规模、主要生产商、主要地区、产品和应用细分研究报告

本文研究全球市场、主要地区和主要国家脱脂小麦胚芽粉的销量、销售收入等&#xff0c;同时也重点分析全球范围内主要厂商&#xff08;品牌&#xff09;竞争态势&#xff0c;脱脂小麦胚芽粉销量、价格、收入和市场份额等。针对过去五年&#xff08;2017-2021&#xff09;年的历史…

能否分析一下我国小麦进口量及对外依存度?

自2011年以后&#xff0c;我国小麦每年都是供大于求&#xff0c;国内完全可以自给自足。 我国小麦的困境主要在于国际市场竞争力很弱&#xff0c;生产成本太高&#xff0c;出口量极少&#xff0c;价格上同美国和俄罗斯相比没有优势。 简单分析一下&#xff1a; 如果你想了解农产…
最新文章