117. 填充每个节点的下一个右侧节点指针 II

给定一个二叉树

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

代码如下：

struct Node* connect(struct Node* root) {
      if (!root) return NULL;
      struct Node currLayerHead = { 0,NULL,NULL, root };;
      struct Node* currLayerHeadCurr = &currLayerHead;
      struct Node nextLayerHead = {0,NULL,NULL, NULL};
      struct Node* nextLayerHeadCurr = &nextLayerHead;

      while (currLayerHeadCurr->next) {
          struct Node* curr = currLayerHeadCurr->next;
          // 1. 将子节点记录到下一次的遍历链表中
          if (curr->left) {
              nextLayerHeadCurr->next = curr->left;
              nextLayerHeadCurr = nextLayerHeadCurr->next;
          }

          if (curr->right) {
              nextLayerHeadCurr->next = curr->right;
              nextLayerHeadCurr = nextLayerHeadCurr->next;
          }
          
          // 2. 处理下一个节点
          currLayerHeadCurr = currLayerHeadCurr->next;

          // 3. 如果当前层为空了，下一层也为空，跳出
          if (currLayerHeadCurr->next == NULL && nextLayerHead.next == NULL) {
              break;
          }

          // 4. 当前层没有要处理的节点了
          if (currLayerHeadCurr->next == NULL) {
              currLayerHead.next = nextLayerHead.next;
              nextLayerHead.next = NULL;
              nextLayerHeadCurr = &nextLayerHead;
              currLayerHeadCurr = &currLayerHead;
              printf("\n");
          }
         
      }

      return root;
  }

思路：遍历当前层的时候，把子节点记录为下一次遍历的下一层，当当前层遍历完的时候，交换当前层和下一层，下一层就为空了。当当前层和下一层的链表都为空的时候，就表示遍历完成了，同时链接也完成了。