29. Populating Next Right Pointers in Each Node && Populating Next Right Pointers in Each Node II

时间:2022-08-26 10:44:34

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的更多相关文章

  1. 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 ...

  2. Node.app – 用于 iOS App 开发的 Node.js 解释器

    Node.app 是用于 iOS 开发的 Node.js 解释器,它允许最大的代码重用和快速创新,占用资源很少,为您的移动应用程序提供 Node.js 兼容的 JavaScript API.你的客户甚 ...

  3. Node.js实战项目学习系列(5) node基础模块 path

    前言 前面已经学习了很多跟Node相关的知识,譬如开发环境.CommonJs,那么从现在开始要正式学习node的基本模块了,开始node编程之旅了. path path 模块提供用于处理文件路径和目录 ...

  4. [Node.js] 00 - Where do we put Node.js

    Ref: 前后端分离的思考与实践(五篇软文) 其实就是在吹淘宝自己的Midway-ModelProxy架构. 第一篇 起因 为了提升开发效率,前后端分离的需求越来越被重视, 同一份数据接口,我们可以定 ...

  5. Node.js 学习笔记(一)--------- Node.js的认识和Linux部署

    Node.js 一.Node.js 简介  简单的说 Node.js 就是运行在服务端的可以解析并运行 JavaScript 脚本的软件. Node.js 是一个基于Chrome JavaScript ...

  6. Node“getTextContent() is undefined for the type Node”处理办法

    最近一个项目在MyEclipse导入后总是报getTextContent() is undefined for the type Node错误. 经过查找原来是因为Node类为JDK中自带的(org. ...

  7. 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 & 登出终 ...

  8. node基础09:第2个node web服务器

    1.同时输出文字与图片 在前几个小课程中,我会学会了 从服务器中读取文字字符,并且向浏览器中输出 从服务器中读取图片文件,并且向浏览器中输出 这节课中,我学会了同时向浏览器输出文字,图片.对此,我感到 ...

  9. [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 ...

随机推荐

  1. 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 二 ...

  2. Web Api 中返回JSON的正确做法

    在使用Web Api的时候,有时候只想返回JSON:实现这一功能有多种方法,本文提供两种方式,一种传统的,一种作者认为是正确的方法. JSON in Web API – the formatter b ...

  3. 2016国产恐怖惊悚《诡娃》HD720P.国语中字

    导演: 蒋国权编剧: 任旭东主演: 李抒航 / 程媛媛 / 孔维类型: 惊悚 / 恐怖制片国家/地区: *语言: 汉语普通话上映日期: 2016-02-25(*)片长: 89分钟诡娃的剧情 ...

  4. CSS3 animation的steps方式过渡

    animation默认以ease方式过渡,它会在每个关键帧之间插入补间动画,所以动画效果 是连贯性的.除了ease,linear.cubic-bezier之类的过渡函数都会为其插入补间. 但有些效果不 ...

  5. BZOJ 1486: [HNOI2009]最小圈( 二分答案 + dfs判负圈 )

    二分答案m, 然后全部边权减掉m, 假如存在负圈, 那么说明有平均值更小的圈存在. 负圈用dfs判断. ------------------------------------------------ ...

  6. yii2自带的backend,frontend不够用,添加一个后台模块怎么做?

    在复杂项目里,高级模板中的fontend.backend application明显不够,可以再添加另外的application. 例如添加一个seller application .步骤如下: 1, ...

  7. android开发常用工具箱

    我的工具包资料目录 我的个人总结,最近做的项目需要了的一些资料,感觉挺乱的,然后现在整理了一下. Jar包 包名 版本号 作用 下载地址 xUtils 2.6.14和3.1.26 大文件上传下载等 旧 ...

  8. 用 Python 鉴别色色的图片

    0 前言 实话实说啊,这个标题起得就有点标题党,识别是识别,准确率就有点玄学了. 1 环境说明 Win10 系统下 Python3,编译器是 Pycharm,需要安装 nonude 这个库. Pych ...

  9. 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 ...

  10. Spring boot 入门篇

    详见:https://www.cnblogs.com/ityouknow/p/5662753.html 什么是Spring Boot Spring Boot 是由 Pivotal 团队提供的全新框架, ...