当前位置:网站首页>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);
}
}
边栏推荐
猜你喜欢
03-SDRAM:写操作(突发)
shell之条件语句(test、if、case)
Zotero | Zotero translator插件更新 | 解决百度学术文献无法获取问题
Postgresql source code learning (34) - transaction log ⑩ - full page write mechanism
Difficulty comparison between high concurrency and multithreading (easy to confuse)
基金投顾业务
完美指南|如何使用 ODBC 进行无代理 Oracle 数据库监控?
HighTec 的安装与配置
金融租赁业务
Zabbix6.2惊喜发布!特别优化中大型环境部署的性能!
随机推荐
Titanic 预测问题
一文读懂 MongoDB 和 MySQL 的差异
【微服务】Nacos集群搭建以及加载文件配置
DirectExchange switch simple introduction demo
Kubernetes scheduling
leetcode 406. Queue Reconstruction by Height
线程唤醒机制
基金投顾业务
Zotero | Zotero translator插件更新 | 解决百度学术文献无法获取问题
opencv、pil和from torchvision.transforms的Resize, Compose, ToTensor, Normalize等差别
小实战项目之——吃货联盟订餐系统
事务的四大特性
[PSQL] SQL基础教程读书笔记(Chapter1-4)
基于交替迭代法的交直流混合系统潮流计算matlab程序iEEE9节点系统算例
自动翻译软件-批量批量自动翻译软件推荐
Conditional statements of shell (test, if, case)
【Go语言入门教程】Go语言简介
Run the NPM will pop up to ask "how are you going to open this file?"
MySql的安装配置超详细教程与简单的建库建表方法
Some derivation formulas for machine learning backpropagation