当前位置:网站首页>2022.07.26_每日一题
2022.07.26_每日一题
2022-07-31 06:07:00 【诺.い】
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 {
// 借用了下先序遍历
// next 指针分两种
// 1
// 2 3
// 4 5 6 7
// 第一种: 2 -> 3 直接让头节点的左孩子指向右孩子即可
// 第二种: 5 -> 6 两棵子树左右孩子直接的指针, 可以利用头节点 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);
}
}
边栏推荐
- tidyverse笔记——管道函数
- Gradle剔除依赖演示
- 新瓶陈酒 --- 矩阵快速幂
- 双倍数据速率同步动态随机存储器(Double Data Rate Synchronous Dynamic Random Access Memory, DDR SDRAM)- 逻辑描述部分
- 第十七章:回溯探求指定入口的马步遍历,贪心无回溯探求马步遍历,递归探求nxm棋盘带障碍马步遍历
- codec2 BlockPool:不可读库
- Foreign trade website optimization - foreign trade website optimization tutorial - foreign trade website optimization software
- 讲解实例+详细介绍@Resource与@Autowired注解的区别(全网最全)
- 事务的传播机制
- Conditional statements of shell (test, if, case)
猜你喜欢
Bulk free text translation
How to use repeating-linear-gradient
Explain the example + detail the difference between @Resource and @Autowired annotations (the most complete in the entire network)
Some derivation formulas for machine learning backpropagation
【云原生】-Docker安装部署分布式数据库 OceanBase
Analysis of pseudo-classes and pseudo-elements
解决安装 Bun 之后出现 zsh compinit: insecure directories, run compaudit for list. Ignore insecure directorie
【 TA - frost Wolf _may - "one hundred plan" 】 art 2.3 hard surface
从 Google 离职,前Go 语言负责人跳槽小公司
【编程题】【Scratch三级】2022.03 冬天下雪了
随机推荐
nohup原理
Difficulty comparison between high concurrency and multithreading (easy to confuse)
安装gstreamer开发依赖库到项目sysroot目录
Analysis of the implementation principle and detailed knowledge of v-model syntactic sugar and how to make the components you develop support v-model
shell之条件语句(test、if、case)
第三方库-store
【科普向】5G核心网架构和关键技术
iOS大厂面试查漏补缺
tidyverse笔记——管道函数
单点登录 思维导图
【Go语言刷题篇】Go完结篇函数、结构体、接口、错误入门学习
SQL Server Datetime2数据类型
机器学习反向传播的一些推导公式
【第四章】详解Feign的实现原理
Run the NPM will pop up to ask "how are you going to open this file?"
解决安装 Bun 之后出现 zsh compinit: insecure directories, run compaudit for list. Ignore insecure directorie
LeetCode刷题——摆动序列#376#Medium
MySQL的触发器
【网络攻防】常见的网络攻防技术——黑客攻防(通俗易懂版)
03-SDRAM:写操作(突发)