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

題意：給一 perfect BT, 其所有 leaf 皆在同一層, 且每個 non-leaf 皆有兩個 child。BT 定義如下:

填充每個 node 的 next, 讓 next 指向其右邊的 node。
若右邊沒有 node, 則指向 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) { // 每層最後一個的 next 不用改(因為預設為 NULL)
                    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：

想法：利用 DFS, 使用 pre-order

  • 先將 root->left->next 指向 root->right
  • 再將 root->right->next 指向 root->next->left(因為先前已經將 root->next 指向其右邊的 node)
  • 然後使用遞迴呼叫 left, right child

e.g. 下圖中

  • 第一次 dfs(root) 的時候已經將 a->next 指向 d

  • 第二次 dfs(a) 時, b 透過 a 指向 c, 且 c 透過 a->next = d 指向 e

class Solution {
public:
    Node* connect(Node* root) {
        // 不判斷 root->right 是因為 perfect BT 中若 root 沒有 left child
        // 則 root 一定不會有 right child
        // 因為下面需存取 root->left->next, 所以必須保證 root->left 不為 null
        if (!root || !root->left) {
            return root;
        }

        root->left->next = root->right;

        if (root->next) { // 執行到這行, root->right 必定不為 null(因為是 perfect BT)
            root->right->next = root->next->left;
        }

        connect(root->left);
        connect(root->right);

        return root;
    }
};
  • time：$O(n)$ ➔ 每個 node 皆被遍歷一次
  • space：$O(log(n))$ ➔ perfect BT 的深度為 $log(n)$

Solution 3：

想法：改進 Solution 2, 用 iterative 的方式將 space 降到 $O(1)$

  • cur 由左至右遍歷第 N 層, 而 nxt 指向第 N + 1 層的第一個 node
  • while loop 中, cur 會將其 child 的 next 指向正確的 node
  • 若 cur 走到第 N 層的結尾, 則 cur 移動到下一層(也就是 nxt)

當 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 *cur = root, *nxt = root->left;

        while (cur && nxt) {
            cur->left->next = cur->right;

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

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

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

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