推荐订阅源

原题地址

大意是，给定二叉树的每个节点都有一个next指针，希望能遍历一遍二叉树使每个节点的next指针指向其同一级的右侧节点（最右侧节点的next指针始终置为空）

如：

         1
       /  \
      2    3
     / \    \
    4   5    7

变换后：

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

基本思路是按层序遍历(BFS)来设置指针。因为有next指针的存在，遍历每层时，该层的next指针已经在上一层设置好，所以只需按照next指向的顺序遍历该层即可。只需常量空间。代码及解释如下：

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

示意图