Populating Next Right Pointers in Each Node II

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/description/

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

You may only use constant extra space.

Thoughts

对二叉树每个结点增加next指针指向每层下一个结点。不难想到按层遍历，对每个结点，假设它所在的层已经连好了，通过它去连接下一层的结点。用pre_c记录上一个被连的结点，用它去连当前结点的子结点，再更新pre_c。当前结点处理好后，直接利用它的next就蹦到本层下一个结点。当next为null时说明本层已经遍历完，下层都已连好，需要一个额外指针next_lev记录下层第一个结点。

Code

/*
 * @lc app=leetcode id=117 lang=cpp
 *
 * [117] Populating Next Right Pointers in Each Node II
 */

// @lc code=start
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() {}

    Node(int _val, Node* _left, Node* _right, Node* _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
class Solution {
public:
    Node* connect(Node* root) {
        Node *cur = root, *pre_c = nullptr, *next_lev = nullptr;
        const auto conn = [&](Node *l) {
            if (l == nullptr) return;
            if (next_lev == nullptr) next_lev = l;
            if (pre_c != nullptr) pre_c->next = l;
            pre_c = l;
        };
        while (cur != nullptr) {
            conn(cur->left);
            conn(cur->right);
            if (cur->next == nullptr) {
                cur = next_lev;
                next_lev = nullptr;
                pre_c = nullptr;
            } else cur = cur->next;
        }
        return root;
    }
};
// @lc code=end

Analysis

Errors:

1. node = node.next忘了写。

做题耗时11min

时间复杂度O(n), 空间复杂度O(1).