【题目】

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 =http://www.mamicode.com/= -1){>



[LeetCode]117.Populating Next Right Pointers in Each Node II