小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Algorithm
  5. Leetcode
  6. 正文

[leetcode]populating next right pointers in each node

2019年4月15日 1088点热度 0人点赞 0条评论

题目描述

题目描述

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

Initially, all next pointers are set toNULL.

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

原理解释

刚开始,我这个题想用递归。但是递归不满足要求(使用线性的额外空间)。所以就不用递归。.
我们可以这样考虑,用两个指针,假设为m和n。可以借鉴层序遍历的思想,我们添加next指针是完成一层厚进行下一层。那么我们就令m来指向每一层的左侧第一个元素,然后让n从左侧第一个元素一直往右进行处理。实际上,我们m和n在第i行的时候,操作的元素是第i+1行,所以当我们操作i+1行的时候,就可以用next指针实现n往右移动了。
所以思路就可以这样:
我们定义m和n,其中m指向root。然后判断当m->left不为空的时候,我们才有必要进行本程序的操作。以下的步骤都是建立在m->left不为空的时候:

  • 我们令n等于m,就是相当于要从当前的m这个节点开始往右操作。当n不为空的时候,我们就直接n->left->next=n->right。建立起如下图所示,红色为当前m和n指向的结点,3就是n->left的结点,4就是n->right的这个节点:

  • 接下里就是连接上图中的4和5直接的结点。首先要判断此时1右侧有没有结点,也就是n->next是否存在(若为根节点就是不存在的),存在的话那么就是n->right->next=n->next->left。这句话还是很容易明白的。即这条紫色的线。

  • 在完成对1的连接之后,n就可以向右移动,对第二个结点进行相同的操作了。所以这个可以写成一个while循环。
  • 当然,为了鲁棒性,开头别忘了一句话检测root是否为空,为空就返回。

下面是实现代码,其中left_point就是上面的m,flag就是上面的n。

代码实现

    void connect(TreeLinkNode *root) {
        if (!root)
            return ;
        TreeLinkNode *left_point=root,*flag;
        while(left_point->left)
        {
            flag=left_point;
            while(flag)
            {
                flag->left->next=flag->right;
                if(flag->next)
                {
                    flag->right->next=flag->next->left;
                }
                flag=flag->next;
            }
            left_point=left_point->left;
        }

    }
本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: leetcode 算法
最后更新:2019年4月15日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程小奥看房之鸿荣源珈誉府论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
新青年报[New Youth]第八期(高考毕业特刊)发布! Java语言程序设计(进阶)(第五章)整理 Welcome to my blog How to use mathjax in hexo 中国大学MOOC-陈越、何钦铭-数据结构-2018春期末考试 今天距离中考还有2天
标签聚合
学习 高中 Python 算法 生活 linux Java 鸟哥的linux私房菜 python学习 leetcode
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 8 个月前(10月20日) :wink:
niming 发布于 9 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号