Populating Next Right Pointers in Each Node
OJ: https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node/
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
思想: 常量空间要求,决定了不能使用递归。满二叉树,简单循环,每次修改一层即可。
/**
* 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) {
TreeLinkNode *p = root;
while(p && p->left) {
p->left->next = p->right;
TreeLinkNode *pre = p, *cur = p->next;
while(cur) {
pre->right->next = cur->left;
cur->left->next = cur->right;
pre = cur;
cur = cur->next;
}
p = p->left;
}
}
};
Populating Next Right Pointers in Each Node II
OJ:https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
- You may only use constant extra space.
For example, Given the following binary tree,
1
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
思想同上: 但是下一层最开始结点和连接过程中链表的第一个结点不易确定,所以需要设定两个变量来保存。
/**
* 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) {
TreeLinkNode *curListNode, *startNode, *curNode;
startNode = root;
while(startNode) {
curNode = startNode;
startNode = curListNode = NULL;
while(curNode) {
if(curNode->left) {
if(startNode == NULL) startNode = curNode->left;
if(curListNode == NULL) curListNode = curNode->left;
else { curListNode->next = curNode->left; curListNode = curListNode->next; }
}
if(curNode->right) {
if(startNode == NULL) startNode =curNode->right;
if(curListNode == NULL) curListNode = curNode->right;
else { curListNode->next = curNode->right; curListNode = curListNode->next; }
}
curNode = curNode->next;
}
}
}
};
29. Populating Next Right Pointers in Each Node && Populating Next Right Pointers in Each Node II的更多相关文章
-
Populating Next Right Pointers in Each Node,Populating Next Right Pointers in Each Node II
Populating Next Right Pointers in Each Node Total Accepted: 72323 Total Submissions: 199207 Difficul ...
-
Node.app – 用于 iOS App 开发的 Node.js 解释器
Node.app 是用于 iOS 开发的 Node.js 解释器,它允许最大的代码重用和快速创新,占用资源很少,为您的移动应用程序提供 Node.js 兼容的 JavaScript API.你的客户甚 ...
-
Node.js实战项目学习系列(5) node基础模块 path
前言 前面已经学习了很多跟Node相关的知识,譬如开发环境.CommonJs,那么从现在开始要正式学习node的基本模块了,开始node编程之旅了. path path 模块提供用于处理文件路径和目录 ...
-
[Node.js] 00 - Where do we put Node.js
Ref: 前后端分离的思考与实践(五篇软文) 其实就是在吹淘宝自己的Midway-ModelProxy架构. 第一篇 起因 为了提升开发效率,前后端分离的需求越来越被重视, 同一份数据接口,我们可以定 ...
-
Node.js 学习笔记(一)--------- Node.js的认识和Linux部署
Node.js 一.Node.js 简介 简单的说 Node.js 就是运行在服务端的可以解析并运行 JavaScript 脚本的软件. Node.js 是一个基于Chrome JavaScript ...
-
Node“getTextContent() is undefined for the type Node”处理办法
最近一个项目在MyEclipse导入后总是报getTextContent() is undefined for the type Node错误. 经过查找原来是因为Node类为JDK中自带的(org. ...
-
nohup /usr/local/node/bin/node /www/im/chat.js >;>; /usr/local/node/output.log 2>;&;1 &;
nohup和&后台运行,进程查看及终止 &后台运行 登出ssh终端,进程会被自动kill掉 但是nohup >>XX.log 2>&1 & 登出终 ...
-
node基础09:第2个node web服务器
1.同时输出文字与图片 在前几个小课程中,我会学会了 从服务器中读取文字字符,并且向浏览器中输出 从服务器中读取图片文件,并且向浏览器中输出 这节课中,我学会了同时向浏览器输出文字,图片.对此,我感到 ...
-
[Node.js] Using npm link to use node modules that are ";in progress";
It is some times convenient, even necessary, to make use of a module that you are working on before ...
随机推荐
-
Spring+SpringMvc+Mybatis框架集成搭建教程一(项目创建)
一.框架搭建环境 Spring 4.2.6.RELEASE SpringMvc 4.2.6.RELEASE Mybatis 3.2.8 Maven 3.3.9 Jdk 1.7 Idea 15.04 二 ...
-
Web Api 中返回JSON的正确做法
在使用Web Api的时候,有时候只想返回JSON:实现这一功能有多种方法,本文提供两种方式,一种传统的,一种作者认为是正确的方法. JSON in Web API – the formatter b ...
-
2016国产恐怖惊悚《诡娃》HD720P.国语中字
导演: 蒋国权编剧: 任旭东主演: 李抒航 / 程媛媛 / 孔维类型: 惊悚 / 恐怖制片国家/地区: *语言: 汉语普通话上映日期: 2016-02-25(*)片长: 89分钟诡娃的剧情 ...
-
CSS3 animation的steps方式过渡
animation默认以ease方式过渡,它会在每个关键帧之间插入补间动画,所以动画效果 是连贯性的.除了ease,linear.cubic-bezier之类的过渡函数都会为其插入补间. 但有些效果不 ...
-
BZOJ 1486: [HNOI2009]最小圈( 二分答案 + dfs判负圈 )
二分答案m, 然后全部边权减掉m, 假如存在负圈, 那么说明有平均值更小的圈存在. 负圈用dfs判断. ------------------------------------------------ ...
-
yii2自带的backend,frontend不够用,添加一个后台模块怎么做?
在复杂项目里,高级模板中的fontend.backend application明显不够,可以再添加另外的application. 例如添加一个seller application .步骤如下: 1, ...
-
android开发常用工具箱
我的工具包资料目录 我的个人总结,最近做的项目需要了的一些资料,感觉挺乱的,然后现在整理了一下. Jar包 包名 版本号 作用 下载地址 xUtils 2.6.14和3.1.26 大文件上传下载等 旧 ...
-
用 Python 鉴别色色的图片
0 前言 实话实说啊,这个标题起得就有点标题党,识别是识别,准确率就有点玄学了. 1 环境说明 Win10 系统下 Python3,编译器是 Pycharm,需要安装 nonude 这个库. Pych ...
-
org.apache.ibatis.binding.BindingException: Invalid bound statement (not found): com.bw.mapper.BillMapper.getBillList 	at org.apache.ibatis.binding.MapperMethod$SqlCommand.<;init>;(MapperMethod.java:225
这个错误是没有找到映射文件 org.apache.ibatis.binding.BindingException: Invalid bound statement (not found): com.b ...
-
Spring boot 入门篇
详见:https://www.cnblogs.com/ityouknow/p/5662753.html 什么是Spring Boot Spring Boot 是由 Pivotal 团队提供的全新框架, ...