一、 题目
对于结构体: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;
}
}
}
};