題目網址：https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/

題意：給一 BT, 其中每一個 node 的定義如下:

將每個 node 的 next 指向其右邊的 node。若不存在右邊的 node, 則 next 應指向 NULL。
所有 next 預設皆為 NULL。

進階：

  • 設計 $O(1)$ space 的演算法
  • 可以使用遞迴解題, 遞迴所用到的 stack space 不算做額外的 space

Solution 1：

想法：利用 BFS

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) {
            return root;
        }

        queue<Node*> q;
        q.emplace(root);

        while (!q.empty()) {
            const int len = q.size();

            for (int i = 0; i < len; ++i) {
                const auto cur = q.front();
                q.pop();

                if (i < len - 1) {
                    cur->next = q.front();
                }

                if (cur->left) {
                    q.emplace(cur->left);
                }

                if (cur->right) {
                    q.emplace(cur->right);
                }
            }
        }

        return root;
    }
};

  • time：$O(n)$ ➔ 每個 node 被遍歷一次
  • space：$O(n)$ ➔ 撇除要返回的 res, 在 while loop 迭代的過程中, q 的元素個數不超過 n

Solution 2：

想法：用 iterative + pointer 的方式將 space 降到 $O(1)$

  • dummy 永遠指向第 N + 1 的第一個 node
  • cur 由左至右遍歷第 N 層, 而 nxt 拜訪第 N + 1 層 node 的前一個 node

當 cur 遍歷第 N 層的時候, nxt 會一邊串接起第 N + 1 層的 next pointer。遍歷完第 N 層的時候, 意味著第 N + 1 層也已經透過 next pointer 串接起來了, 這時候 cur 再往第 N + 1 層移動

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) {
            return root;
        }

        Node *dummy = new Node(0);
        Node *cur = root, *nxt = dummy;

        while (cur) {
            if (cur->left) {
                nxt->next = cur->left;
                nxt = nxt->next;
            }

            if (cur->right) {
                nxt->next = cur->right;
                nxt = nxt->next;
            }

            // cur 的 child 已經做完, 移動到下一個 node (cur 右邊的 node)
            cur = cur->next;

            // cur 走到第 N 層的 end, 則 cur 指向第 N + 1 層
            if (!cur) {
                cur = dummy->next;
                nxt = dummy; // 重置 nxt
                dummy->next = nullptr; // 重置 dummy->next
            }
        }

        return root;
    }
};
  • time：$O(n)$ ➔ 每個 node 被遍歷一次
  • space：$O(1)$ ➔ 只需常數空間