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

【分析】

【代码】

/*********************************
*   日期:2014-12-24
*   作者:SJF0115
*   题目: 117.Populating Next Right Pointers in Each Node II
*   来源:https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/
*   结果:AC
*   来源:LeetCode
*   总结:
**********************************/
#include <iostream>
#include <queue>
using namespace std;

struct TreeLinkNode {
    int val;
    TreeLinkNode *left;
    TreeLinkNode *right;
    TreeLinkNode *next;
    TreeLinkNode(int x):val(x),left(NULL),right(NULL),next(NULL){}
};

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(root == NULL){
            return;
        }//if
        queue<TreeLinkNode*> cur;
        queue<TreeLinkNode*> next;
        cur.push(root);
        TreeLinkNode *p,*pre;
        while(!cur.empty()){
            pre = NULL;
            // 当前层遍历
            while(!cur.empty()){
                // 出队列
                p = cur.front();
                cur.pop();
                // 横向连接
                if(pre != NULL){
                    pre->next = p;
                }//if
                pre = p;
                // next保存下一层节点
                // 左子树不空加入队列
                if(p->left){
                    next.push(p->left);
                }//if
                // 右子树不空加入队列
                if(p->right){
                    next.push(p->right);
                }//if
            }//while
            p->next = NULL;
            swap(next,cur);
        }//while
    }
};

//按先序序列创建二叉树
int CreateBTree(TreeLinkNode*& T){
    int data;
    //按先序次序输入二叉树中结点的值,-1表示空树
    cin>>data;
    if(data == -1){
        T = NULL;
    }
    else{
        T = new TreeLinkNode(data);
        //构造左子树
        CreateBTree(T->left);
        //构造右子树
        CreateBTree(T->right);
    }
    return 0;
}
// 输出
void LevelOrder(TreeLinkNode *root){
    if(root == NULL){
        return;
    }//if
    TreeLinkNode *p = root,*q;
    while(p){
        q = p;
        // 横向输出
        while(q){
            cout<<q->val<<"->";
            q = q->next;
        }//while
        if(q == NULL){
            cout<<"NULL"<<endl;
        }//if
        p = p->left;
    }//while
}

int main() {
    Solution solution;
    TreeLinkNode* root(0);
    CreateBTree(root);
    solution.connect(root);
    LevelOrder(root);
}

时间: 2024-09-16 23:13:17

[LeetCode]117.Populating Next Right Pointers in Each Node II的相关文章

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

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 All in One 题目讲解汇总(持续更新中...)

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

LeetCode总结【转】

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

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

libxml2的安装及使用[总结]

1.前言 xml广泛应用于网络数据交换,配置文件.Web服务等等.近段时间项目中做一些配置文件,原来是用ini,现在改用xml.xml相对来说可视性更为直观,很容易看出数据之间的层次关系.关于xml的详细介绍可以参考http://baike.baidu.com/view/159832.htm?fromId=63.本文重点介绍解析xml的libxml2库的安装及使用,举例说明创建和解析xml的过程. 2.libxml2的安装 关于libxml2的介绍请参考官方网址http://xmlsoft.or

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