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