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

C++实现代码(使用层次遍历的方法,每次记录一层,对每一层的next进行赋值):

#include<iostream>
#include<new>
#include<vector>
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;
        vector<TreeLinkNode*> q;
        vector<TreeLinkNode*> curq;
        q.push_back(root);
        TreeLinkNode *tmp;
        while(!q.empty())
        {
            curq=q;
            q.clear();
            for(size_t i=0;i<curq.size();i++)
            {
                tmp=curq[i];
                if(i<curq.size()-1)
                    tmp->next=curq[i+1];
                else
                    tmp->next=NULL;
                if(tmp->left)
                    q.push_back(tmp->left);
                if(tmp->right)
                    q.push_back(tmp->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);
}

 

 

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

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

[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

[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

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,

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上所有的题目,并且贴上了博主的解法,随时随地都能

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" %> <

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的不同的方法,我们可以选择其一.通过本