Populating Next Right Pointers in Each Node 设置二叉树的next节点
2024-09-29 04:28:27
Given a binary tree
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL
.
Initially, all next pointers are set to NULL
.
Note:
- You may only use constant extra space.
- You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
1
/ \
2 3
/ \ / \
4 5 6 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ / \
4->5->6->7 -> NULL
题目要求是一个二叉树每个节点包含三个指针元素,每个节点除了左子树和右子树,还有一个指向其同层次的相邻右侧节点,
若同层次右侧没有节点,则将next设置为空,否则将next设置为右侧相邻节点。
解决思路:
一次对每个节点进行遍历,若左右子树不为空,则将左子树的next指向右子树,若该节点的next为空,则将右子树的next设置为空(看图分析)
若该节点的next不为空,则指向与该节点同层次中相邻的右侧节点的左子树(看图分析)
这里使用一个队列,将根节点先放入队列,从队列中取出一个节点node,node移除队列,node子树的next节点处理按照上面分析操作。
代码如下:
/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
void connect(TreeLinkNode *root) {
if(root == NULL) return;
queue<TreeLinkNode *> q; root->next = NULL; q.push(root); while(!q.empty()){
TreeLinkNode *node = q.front();
q.pop(); if(node->left != NULL && node->right != NULL){
q.push(node->left);
q.push(node->right); node->left->next = node->right;
if(node->next == NULL)
node->right->next = NULL;
else{
TreeLinkNode *node_next = q.front();
node->right->next = node_next->left;
} } } }
};
最新文章
- 2016-1-1最新版本的linphone-android在mac上编译通过,同时建立了IDEA工程
- ShareDrop – 苹果 AirDrop 服务的 HTML5 实现
- 【原】iOS学习39网络之数据请求
- 解决在国内更新android sdk时连不到服务器的问题
- JavaScript 遗漏知识再整理;错误处理,类型转换以及获取当前时间、年份、月份、日期;
- Centos6.5(final)安装gcc和g++,python以及导致问题的解决方法
- ASP.NET的票据工具类FormsAuthenticationTicket
- LoadRunner学习记录--Flights打开空白页的问题
- sendkeys用法详解
- Windows Embedded Compact 2013升级:VS2013也能编译
- MVC小系列(一)【制作表格】
- tomcat配置文件server.xml详解 转载http://blog.csdn.net/yuanxuegui2008/article/details/6056754
- Intent七在属性之一:ComponentName
- C语言:全局变量在多个c文件中公用的方法 [转]
- MS10_087漏洞学习研究
- Webpack 2 视频教程 011 - Webpack2 中加载 CSS 的相关配置与实战
- java实现二叉树的建立以及实现二叉查找树的查、插、删、遍历
- 洛谷 P2820 局域网
- eclipse中文乱码修改新方法
- centos的基本操作