一、 题目

对于结构体:struct TreeLinkNode {

TreeLinkNode *left;

TreeLinkNode *right;

TreeLinkNode *next;

}

填充所有的结点如果存在右侧的节点，则指上(next)右节点；如果没有右侧的节点，那么就指上NULL，最初都指上NULL。

提示:只能使用给定的空间，并且你可以认为给定的二叉树是一个完美的二叉树。

例如：

1

/ \

2 3

/ \ \

4 5 7

处理后:

1 -> NULL

/ \

2 -> 3 -> NULL

/ \ \

4-> 5 -> 7 -> NULL

二、 分析

1、 空节点就直接返回

2、 左节点非空则连接右节点

3、 子节点连接兄弟节点的子节点，则root.right.next = root.next.left;

/**
 * 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;
        if(root->left!=NULL) root->left->next=root->right;
        if(root->right!=NULL&&root->next!=NULL)
        	root->right->next=root->next->left;
        	
        connect(root->left);
        connect(root->right);
    }
};


BFS
/**
 * 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) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        //breadth-first traversal
        queue
  
    bfsq;
        int levelCnt=0;
        int level2=0;
        
        if(root==NULL) return;
        bfsq.push(root);
        levelCnt++;
        TreeLinkNode *prevList=NULL;
        TreeLinkNode *topS=NULL;
        
        while(!bfsq.empty()) 
        {
            topS=bfsq.front();
            bfsq.pop();
            levelCnt--;
        
            if(topS->left!=NULL && topS->right!=NULL)
            {   
                bfsq.push(topS->left);
                level2++;
                bfsq.push(topS->right);
                level2++;
            }
            
            if(prevList!=NULL)
                prevList->next=topS;
            prevList=topS;
            
            if(levelCnt==0)
            {
                levelCnt=level2;
                level2=0;
                prevList=NULL;
            }
            
        }
    }
};