1 using namespace std;
 2 
 3 struct TreeLinkNode {
 4 int val;
 5 TreeLinkNode *left, *right, *next;
 6 TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 7 };
 8 
 9 class Solution {
10 public:
11     void connect(TreeLinkNode *root) {
12         TreeLinkNode *parentLevelPtr = root;
13         TreeLinkNode *pseudoNode = new TreeLinkNode(0);
14         TreeLinkNode *childLevelHead, *childLevelPtr;
15         // 分别为父子层节点准备两套指针，父节点层指针parentLevelPtr按父节点层的next指针往后走。
16         for(; parentLevelPtr != NULL; pseudoNode->next = NULL){ // 每次循环结束需要重置pseudoNode的next指针，否则遍历到叶子节点层时循环无法结束
17             // 子节点层两个指针childLevelHead和childLevelPtr，初始置为指向一个虚拟节点。使用虚拟节点的好处是不用在循环体内判断是否需要给head赋值。
18             childLevelPtr = childLevelHead = pseudoNode;
19             for(; parentLevelPtr; parentLevelPtr = parentLevelPtr->next){
20                 // 父节点指针每移动一次，判断父节点是否有左右儿子，若有则将childLevelPtr的next置为此儿子节点，并将childLevelPtr移至next。
21                 if(parentLevelPtr->left){
22                     childLevelPtr->next = parentLevelPtr->left;
23                     childLevelPtr = childLevelPtr->next;
24                 }
25                 
26                 if(parentLevelPtr->right){
27                     childLevelPtr->next = parentLevelPtr->right;
28                     childLevelPtr = childLevelPtr->next;
29                 }
30             }
31             // 父层遍历完毕，将父层节点指向儿子层继续下一轮
32             parentLevelPtr = childLevelHead->next;
33         }
34         delete pseudoNode;
35     }
36 };