【题目】

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);
}