当前位置:网站首页>2022.07.26_Daily Question
2022.07.26_Daily Question
2022-07-31 07:40:00 【No. い】
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, 212 - 1] 范围内
-1000 <= node.val <= 1000
进阶:
你只能使用常量级额外空间.
使用递归解题也符合要求,本题中递归程序占用的栈空间不算做额外的空间复杂度.
coding
/* // 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 {
// Borrowed from next preorder traversal
// next There are two pointers
// 1
// 2 3
// 4 5 6 7
// 第一种: 2 -> 3 Just let the left child of the head node point to the right child
// 第二种: 5 -> 6 Two subtrees are left and right child direct pointers, Head nodes can be used 2 的 next 指针指向 3, 然后 5 指向 3 的左孩子即可
public Node connect(Node root) {
preOrderRecur(root);
return root;
}
public void preOrderRecur(Node node) {
if (node == null) {
return;
}
if (node.left != null) {
node.left.next = node.right;
node.right.next = node.next == null ? null : node.next.left;
}
preOrderRecur(node.left);
preOrderRecur(node.right);
}
}
边栏推荐
- 2022.07.13_每日一题
- 测试 思维导图
- 【网络攻防】常见的网络攻防技术——黑客攻防(通俗易懂版)
- 零样本学习&Domain-aware Visual Bias Eliminating for Generalized Zero-Shot Learning
- 360推送-360推送工具-360批量推送工具
- Foreign trade website optimization - foreign trade website optimization tutorial - foreign trade website optimization software
- SQLite数据库连接字符串
- 单点登录 思维导图
- 我开发了一个利用 Bun 执行 .ts / .js 文件的 VS Code 插件
- Web浏览器工作流程解析
猜你喜欢
Zotero | Zotero translator plugin update | Solve the problem that Baidu academic literature cannot be obtained
【面试:并发篇38:多线程:线程池】ThreadPoolExecutor类的基本概念
Bulk free text translation
剑指offer(一)
Some derivation formulas for machine learning backpropagation
嵌入式系统驱动初级【2】——内核模块下_参数和依赖
任务及任务切换
【愚公系列】2022年07月 Go教学课程 022-Go容器之字典
03-SDRAM: Write operation (burst)
【Go语言刷题篇】Go完结篇函数、结构体、接口、错误入门学习
随机推荐
事务的传播机制
【 TA - frost Wolf _may - "one hundred plan" 】 art 2.3 hard surface
leetcode 406. Queue Reconstruction by Height
第十六章:构建n(5,7)阶素数幻方
【并发编程】ReentrantLock的lock()方法源码分析
postgresql源码学习(34)—— 事务日志⑩ - 全页写机制
英语翻译软件-批量自动免费翻译软件支持三方接口翻译
文件 - 02 上传文件:上传临时文件到服务器
Kubernetes scheduling
[PSQL] SQL基础教程读书笔记(Chapter1-4)
PCB抄板
文件 - 05 下载文件:根据文件Id下载文件
How to use repeating-linear-gradient
van-uploader上传图片,使用base64回显无法预览的问题
【面试:并发篇38:多线程:线程池】ThreadPoolExecutor类的基本概念
【C语言项目合集】这十个入门必备练手项目,让C语言对你来说不再难学!
Postgresql source code learning (34) - transaction log ⑩ - full page write mechanism
HighTec 的安装与配置
【Go】Go 语言切片(Slice)
【编程题】【Scratch三级】2022.03 冬天下雪了