【树】Populating Next Right Pointers in Each Node
2024-08-24 07:45:26
题目:
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指向后一个节点,使用队列辅助层序遍历时,在队列中用NULL来分割每层的节点。
/**
* Definition for binary tree with next pointer.
* function TreeLinkNode(val) {
* this.val = val;
* this.left = this.right = this.next = null;
* }
*/ /**
* @param {TreeLinkNode} root
* @return {void} Do not return anything, modify tree in-place instead.
*/
var connect = function(root) {
if(root==null){
return;
} var stack=[],pre=null;
stack.push(root);
stack.push(null); while(stack.length!=0){
var p=stack.unshift(); if(p!=null){
if(p.left){
stack.push(p.left);
}
if(p.right){
stack.push(p.right);
}
}else{
if(stack.length!=0){
stack.push(null);
}
} if(pre!=null){
pre.next=p;
} pre=p;
}
};
最新文章
- AWS的SysOps认证考试样题解析
- [QT学习]拷贝文件
- 再谈扩展方法,从string.IsNullOrEmpty()说起
- C4.5决策树--Java
- PHP组合模式
- light oj 1138 - Trailing Zeroes (III)【规律&;&;二分】
- Java设计模式09:单例模式的强化(控制实例个数n)
- linux下面的查找
- 由Python的super()函数想到的
- Linux批量重命名文件
- javascript语句语义大全(2)
- 读Zepto源码之Callbacks模块
- 多重外键关系在java中的处理方案
- 【HTML5】增强的表单
- C++负数取模
- 转: Qt信号槽实现原理 清晰明了
- BSOJ 5603 -- 【SNOI2017】炸弹
- 【python】异步IO
- JAVA多线程17个问题
- MySQL5.5登录密码忘记了,怎嘛办?
热门文章
- 通过wsdl生成client 的几种方式
- PHP数据库抽象层--PDO(PHP Data Object) [一]
- (欧拉公式 很水) Coprimes -- sgu -- 1002
- ZOJ2417 Lowest Bit 2017-04-18 20:53 38人阅读 评论(0) 收藏
- 谷类 cereal
- spring的事务传播属性
- ABP框架入门踩坑-添加实体
- Lucene.net 全文检索数据库
- Swift实战-小QQ(第3章):QQ主界面布局
- LinkedBlockingQueue源码解析(1)