基于层序遍历

第一次看，我们想到的思路肯定都是层序遍历，但是题目要求必须空间复杂度O(1)，所以不能层序遍历。我们还是对上面一题的做法进行改进。

1.还是用每层最左边的节点去更新下一层的next

2.把下一层看成一个单链表，遍历当前层，我们用一个虚拟头节点将下一层的节点链接起来

3.每次更新完下一层的next后，我们再跳到下一层的最左边的节点。

$ 时间复杂度O(N), 空间复杂度O(1)$

参考文献

lc究极班

AC代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return root;
        auto cur = root;
        while (cur){
            auto dummy = new Node(-1);
            auto t = dummy;
            //将下一层变成单链表
            for (auto p = cur ; p ; p = p->next){
                if (p->left) t = t->next = p->left;
                if (p->right) t = t->next = p->right;
            }
            cur = dummy->next;//跳到下一层最左边的结点
        }

        return root;
    }
};