今天要來探討的是 Leetcode Leetcode #117 Populating Next Right Pointers in Each Node II 。

方法 1 BFS

經典的 Binary Tree Level Order traversal ，可以視為 Leetcode #102 的變化題。

class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr) return root;
        queue<Node*> qu;
        qu.push (root);
        while (!qu.empty()) {
            int size = qu.size();
            for (int i=0; i<size; i++) {
                Node* curr = qu.front();
                qu.pop();
                if (curr->left != nullptr) qu.push(curr->left);
                if (curr->right != nullptr) qu.push(curr->right);

                if (i == size-1) {
                    curr->next = nullptr;
                } else {
                    curr->next = qu.front();
                }
            }
        }
        return root;
    }
};

Time Complexity O(n)

Space Complexity O(n)

方法 2 Better Space consumption

優化第一個做法，嘗試再降低空間複雜度，方法 1 中透過 queue 來做 level order traversal ，這是耗費最大記憶體空間的原因，思考是否能夠不使用 queue 。

原本需要使用 queue 是因為走訪 binary tree 過程中，我們並不知道哪些 nodes 屬於同一 level，因此會利用 BFS 方式將同一 level 的 nodes 儲存到 queue 裡 ，再將 queue 裡的 nodes 串聯起來。

但這一題多了一個 next pointer ，next pointer 會串聯同一 level 的 nodes ，可以借助 next pointer 來取代 queue 。

當走訪於 level N 的時候，會一邊串聯起 level N+1 的 next pointer ，走訪完 level N 時候，意味著 level N+1 也透過 next pointer 串起了，這時候可以再往 level N+1 移動，只要將這樣過程轉換為程式碼即可。

在過程中需要 3 個 pointer 來協助:

1. Node *level_walker : 協助走訪 level N 的 nodes 。
2. Node *next_level_walker : 用來串連 level N+1 的 nodes 。
3. Node *dummy_head : 可以視為一個 dummy node ，這個節點的 next pointer 永遠指向 level N+1 的第一個節點，當一層的 nodes 走訪完畢，就可以透過此 pointer 知道下一層的第一個節點。

class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr) return root;
        Node *dummy_head = new Node();
        Node *next_level_walker = dummy_head;
        Node *level_walker = root;

        while (level_walker != nullptr) {
            if (level_walker->left != nullptr) {
                next_level_walker->next = level_walker->left;
                next_level_walker = next_level_walker->next;
            }
            if (level_walker->right != nullptr) {
                next_level_walker->next = level_walker->right;
                next_level_walker = next_level_walker->next;
            }
            // One node and its subtree done. Move to next node.
            level_walker = level_walker->next;

            // Walks to the end the level N
            if (level_walker == nullptr) {
                level_walker = dummy_head->next;
                next_level_walker = dummy_head;
                dummy_head->next = nullptr;
            }
        }
        return root;
    }
};