当前位置:网站首页>LeetCode 116. 填充每个节点的下一个右侧节点指针
LeetCode 116. 填充每个节点的下一个右侧节点指针
2022-04-23 20:23:00 【亡于灬】
116. 填充每个节点的下一个右侧节点指针
1)题目描述
给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
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]
范围内 -1000 <= node.val <= 1000
2)分析
递归。
首先考虑根结点为空,直接返回空指针。
当根结点不为空的时候,考虑根结点有叶子结点。那么左叶子结点的next
指向右叶子结点。
考虑当前根结点存在父结点,那么当前根结点一定有兄弟结点(参照FigureB
中的2
),那么当前根结点的右叶子结点(参照FigureB
中的5
)的next
就应该指向当前根结点next
所指结点(参照FigureB
中的3
)的左叶子结点(参照FigureB
中的6
)。
3)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 {
public:
Node* connect(Node* root) {
if(!root)
return NULL;
if(root->left){
root->left->next=root->right;
if(root->next)
root->right->next=root->next->left;
}
connect(root->left);
connect(root->right);
return root;
}
};
版权声明
本文为[亡于灬]所创,转载请带上原文链接,感谢
https://blog.csdn.net/qq_38342510/article/details/124360289
边栏推荐
- DTMF双音多频信号仿真演示系统
- [talkative cloud native] load balancing - the passenger flow of small restaurants has increased
- DTMF dual tone multi frequency signal simulation demonstration system
- LeetCode 232、用栈实现队列
- 三十一. `prototype`显示原型属性和`__proto__`隐式原型属性
- star
- Es keyword sorting error reason = fielddata is disabled on text fields by default Set fielddata = true on keyword in order
- Change the material of unity model as a whole
- Matlab analytic hierarchy process to quickly calculate the weight
- CVPR 2022 | querydet: use cascaded sparse query to accelerate small target detection under high resolution
猜你喜欢
PIP installation package reports an error. Could not find a version that satisfies the requirement pymysql (from versions: none)
Five minutes to show you what JWT is
LeetCode 994、腐烂的橘子
2022DASCTF Apr X FATE 防疫挑战赛 CRYPTO easy_real
Matlab analytic hierarchy process to quickly calculate the weight
上海回應“面粉官網是非法網站”:疏於運維被“黑”,警方已立案
LeetCode 542、01 矩阵
Leetcode dynamic planning training camp (1-5 days)
Identification of bolt points in aerial photography based on perception
DNS cloud school | quickly locate DNS resolution exceptions and keep these four DNS status codes in mind
随机推荐
Numpy mathematical function & logical function
JDBC tool class jdbcfiledateutil uploads files and date format conversion, including the latest, simplest and easiest way to upload single files and multiple files
波场DAO新物种下场,USDD如何破局稳定币市场?
Analysis of the relationship between generalized Bim and CAD under the current background
What is the difference between a host and a server?
Automatically fill in body temperature and win10 task plan
Notes of Tang Shu's grammar class in postgraduate entrance examination English
Matlab analytic hierarchy process to quickly calculate the weight
PIP installation package reports an error. Could not find a version that satisfies the requirement pymysql (from versions: none)
Commit and ROLLBACK in DCL of 16mysql
16MySQL之DCL 中 COMMIT和ROllBACK
上海回应“面粉官网是非法网站”:疏于运维被“黑”,警方已立案
Azkaban recompile, solve: could not connect to SMTP host: SMTP 163.com, port: 465 [January 10, 2022]
I JS deep copy and shallow copy
DNS cloud school rising posture! Three advanced uses of authoritative DNS
Commit and rollback in DCL of 16 MySQL
The ODB model calculates the data and outputs it to excel
考研英语唐叔的语法课笔记
Solution to PowerDesigner's failure to connect to MySQL in x64 system
上海回應“面粉官網是非法網站”:疏於運維被“黑”,警方已立案