116. Populating Next Right Pointers in Each Node (Tree; WFS)
2024-10-20 12:47:46
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指针,我们只需记录每层最左的节点,所以可以做到use constant extra space
class Solution {
public:
void connect (TreeLinkNode *root){
TreeLinkNode* parent;
TreeLinkNode* current;
TreeLinkNode* nextParent = root;
while(nextParent){ //new level started
parent = nextParent;
nextParent = parent->left;
current = nextParent;
if(!current) return; //add next pointer
current->next = parent->right;
current = current->next;
if(!current) return;
while(parent->next){
parent = parent->next;
current->next = parent->left;
current = current->next;
if(!current) return;
current->next = parent->right;
current = current->next;
if(!current) return;
}
}
}
};
最新文章
- oracle 存储过程 包 【转】
- fir.im Weekly - 2015 年开发者调查报告
- Codeforces Round #246 (Div. 2) B. Football Kit
- cookie 的“Value”=“xxxxx,xxxxx”部分无效
- 响应式Web设计 – 布局
- Serialize and Deserialize Binary Tree
- jquery 下了框
- lighttpd fastcgi的搭建
- [转载]C#对象序列化与反序列化
- OpenCV中的常用函数
- Windows Azure 社区新闻综述(#68 版)
- ios 按钮常见属性
- Installshield 64位操作系统下拷贝文件,如何重定向到32位的系统文件夹下
- java学习笔记 --- 面向对象3
- 201521123012 《Java程序设计》第二周学习总结
- Linux运维人员共用root帐户权限审计(转至马哥Linux运维)
- Express全系列教程之(七):cookie的加密
- 第一个jQuery
- Java 连接MongoDB集群的几种方式
- PythonStudy——字符串类型 String type
热门文章
- 201621123005《Java程序设计》第六次学习总结
- 如何在CentOS7上安装MySQL并实现远程访问
- iis6 , URL重写HTM文件名后,出现真实的HTM文件不能访问的解决
- Caused by: java.lang.NoClassDefFoundError: Could not initialize class org.elasticsearch.threadpool.ThreadPool
- 《FDTD electromagnetic field using MATLAB》读书笔记之一阶、二阶偏导数差商近似
- http的报文结构和状态码的含义
- 51nod 算法马拉松4 B递归(YY)
- test20181019 B君的第二题
- windows7安装django并创建第一个应用
- 使用C++生成1-33中的6个随机数,无重复