原题地址（中等）

方法1—队列+层次遍历

思路

用队列模拟层次遍历，再加一些处理，可以非常容易的做出来。
然并卵，我开始没看到题目的要求是空间需要常数级，所以这种用队列的做法，是不符合题意的。。。

代码

  1. class Solution {
  2. public:
  3.     Node* connect(Node* root) {
  4.         if(!root)   return NULL;
  5.         queue<Node*> q;
  6.         q.push(root);
  7.         while(!q.empty()) {
  8.             int count = q.size();
  9.             Node* pre = NULL;
  10.             while(count) {
  11.                 count--;
  12.                 Node* p = q.front();
  13.                 q.pop();
  14.                 if(pre) pre->next = p;
  15.                 pre = p;
  16.                 if(p->left) q.push(p->left);
  17.                 if(p->right) q.push(p->right);
  18.             }
  19.         }
  20.         return root;
  21.     }
  22. };

时间复杂度

把所有结点都遍历且仅遍历了一次，所以为 O(N)

空间复杂度

O(N) ，也就是队列的空间代价

方法2—利用next

**

思路

可以利用next指针来免去队列的空间存储

只要每次都能找到第 i 层的最左侧结点，并且预先把第 i 层的所有结点都连接起来，那么就可以遍历第 i 层。

我们就用这个思路，在遍历第 i-1 层的时候，把第 i 层都连接好，并且记录下第 i 层的第一个结点，这样就可以实现层次遍历了。

代码

class Solution {
public:
    Node* connect(Node* root) {
        Node* start = root;
        while(start) {
            Node* pre = NULL, *nextStart = NULL;
            for(auto p = start; p != NULL; p = p->next) {
                if(p->left) {
                    if(pre) pre->next = p->left;
                    pre = p->left;
                    if(!nextStart)  nextStart = p->left;
                }
                if(p->right) {
                    if(pre) pre->next = p->right;
                    pre = p->right;
                    if(!nextStart)  nextStart = p->right;
                }
            }
            start = nextStart;
        }
        return root;
    }
};

时间复杂度

O(N)

空间复杂度

O(1)