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

思路:主要是使用层次遍历,将所有结点按照层次遍历的操作将前一个出队列的结点的next域指向队首元素,即下一个要访问的结点,这样就将所有结点连成一串了,然后将所有一直靠右的子树的next置位NULL。

 

C++实现代码如下:

#include<iostream>
#include<new>
#include<queue>
using namespace std;

// 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)
    {
        if(root==NULL)
            return;
        queue<TreeLinkNode*> q;
        q.push(root);
        TreeLinkNode *tmp=root;
        while(!q.empty())
        {
            tmp->next=q.front();
            tmp=q.front();
            q.pop();
            if(tmp->left)
                q.push(tmp->left);
            if(tmp->right)
                q.push(tmp->right);
        }
        tmp->next=NULL;
        while(root)
        {
            root->next=NULL;
            root=root->right;
        }
    }
    void createTree(TreeLinkNode *&root)
    {
        int i;
        cin>>i;
        if(i!=0)
        {
            root=new TreeLinkNode(i);
            if(root==NULL)
                return;
            createTree(root->left);
            createTree(root->right);
        }
    }
};

int main()
{
    Solution s;
    TreeLinkNode *root;
    s.createTree(root);
    s.connect(root);
    cout<<root->val<<endl;
    while(root->left)
    {
        cout<<root->left->val<<" ";
        TreeLinkNode *tmp=root->left->next;
        while(tmp)
        {
            cout<<tmp->val<<" ";
            tmp=tmp->next;
        }
        cout<<endl;
        root=root->left;
    }
}

运行结果:

 

时间: 2024-09-21 10:25:23

Populating Next Right Pointers in Each Node的相关文章

[LeetCode]116.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. Initiall

[LeetCode]117.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 bin

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

ajax-求高受!$.each嵌套$.each出现这样的问题,并且js无效果

问题描述 求高受!$.each嵌套$.each出现这样的问题,并且js无效果 <%@ page language="java" contentType="text/html; charset=utf-8" pageEncoding="utf-8"%> <%@taglib uri="http://java.sun.com/jsp/jstl/core" prefix="c" %> <

leetcode难度及面试频率

转载自:LeetCode Question Difficulty Distribution               1 Two Sum 2 5 array sort         set Two Pointers 2 Add Two Numbers 3 4 linked list Two Pointers           Math 3 Longest Substring Without Repeating Characters 3 2 string Two Pointers      

LeetCode总结【转】

转自:http://blog.csdn.net/lanxu_yy/article/details/17848219 版权声明:本文为博主原创文章,未经博主允许不得转载. 最近完成了www.leetcode.com的online judge中151道算法题目.除各个题目有特殊巧妙的解法以外,大部分题目都是经典的算法或者数据结构,因此做了如下小结,具体的解题思路可以搜索我的博客:LeetCode题解 题目 算法 数据结构 注意事项 Clone Graph BFS 哈希表 Word Ladder II

LeetCode All in One 题目讲解汇总(持续更新中...)

终于将LeetCode的免费题刷完了,真是漫长的第一遍啊,估计很多题都忘的差不多了,这次开个题目汇总贴,并附上每道题目的解题连接,方便之后查阅吧~ 如果各位看官们,大神们发现了任何错误,或是代码无法通过OJ,或是有更好的解法,或是有任何疑问,意见和建议的话,请一定要在对应的帖子下面评论区留言告知博主啊,多谢多谢,祝大家刷得愉快,刷得精彩,刷出美好未来- 博主制作了一款iOS的应用"Leetcode Meet Me",里面有Leetcode上所有的题目,并且贴上了博主的解法,随时随地都能

C Programming for Embedded System

Introduction Now for embedded system development people are using operating system to add more features and at the same time reduce the development time of a complex system. This article gives a simple & understandable overview of scheduling techniqu

Ubuntu 15.04下安装Node.JS的不同方式

如果你要在Ubuntu 15.04上安装Node.js的话,这篇教程对你来说肯定很重要.Node.js从本质上来说就是一个运行在服务端上的封装好了输入输出流的javascript程序.Node.js巧妙的使用单线程的事件循环来处理高吞吐量和非阻塞IO.同时它也是一个提供了通过操作系统读写文件和网络操作功能的平台层.所以这篇文章将展示在Ubuntu 15.04 server上不同的安装Node.Js的方式. 安装Node.JS 的方法 有许多安装Node.JS的不同的方法,我们可以选择其一.通过本