当前位置:网站首页>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);
}
}
边栏推荐
- 简单谈谈Feign
- 金融租赁业务
- Leetcode952. 按公因数计算最大组件大小
- 我开发了一个利用 Bun 执行 .ts / .js 文件的 VS Code 插件
- 庐山谣寄卢侍御虚舟
- 项目 - 如何根据最近30天、最近14天、最近7天、最近24小时、自定义时间范围查询MySQL中的数据?
- Postgresql source code learning (34) - transaction log ⑩ - full page write mechanism
- Zero-Shot Learning & Domain-aware Visual Bias Eliminating for Generalized Zero-Shot Learning
- SQL Server Datetime2数据类型
- 文件 - 03 下载文件:根据文件id获取下载链接
猜你喜欢
随机推荐
【第四章】详解Feign的实现原理
解决win11/win10在登陆界面(解锁界面)点击获取每日壁纸无效的问题 - get Daily Lockscreen and Wallpaper - Win11/10的登录界面背景图片在哪里?
【微服务】(十六)—— 分布式事务Seata
那些破釜沉舟入局Web3.0的互联网精英都怎么样了?
SQL Server Datetime2数据类型
2022.07.14_每日一题
科普 | “大姨太”ETH 和 “小姨太”ETC的爱恨情仇
2022.07.12_每日一题
《白帽子说Web安全》思维导图
文件 - 03 下载文件:根据文件id获取下载链接
Kubernetes scheduling
Obtaining server and client information
Run the NPM will pop up to ask "how are you going to open this file?"
Chapter 17: go back to find the entrance to the specified traverse, "ma bu" or horse stance just look greedy, no back to search traversal, "ma bu" or horse stance just look recursive search NXM board
线程中断方法
【Go语言入门教程】Go语言简介
Zero-Shot Learning & Domain-aware Visual Bias Eliminating for Generalized Zero-Shot Learning
【Star项目】小帽飞机大战(八)
Zotero | Zotero translator plugin update | Solve the problem that Baidu academic literature cannot be obtained
庐山谣寄卢侍御虚舟