Populating Next Right Pointers in Each Node ใน C++: เชื่อม Next Pointer ต้นไม้ Complete Binary Tree

อัลกอริทึมเดียวกันทำงานได้เพราะ Complete Tree เป็นกรณีพิเศษของ General Tree

ขั้นตอน (เหมือน Node II)

1. pre = root, nextPre = nullptr, prev = nullptr
2. while pre:
   • while pre:
     • เชื่อม pre->left และ pre->right ตามลำดับ
     • pre = pre->next
   • pre = nextPre; nextPre = prev = nullptr

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int val;
    Node *left, *right, *next;
    Node() : val(0), left(nullptr), right(nullptr), next(nullptr) {}
    Node(int _val, Node* _left, Node* _right) : val(_val), left(_left), right(_right), next(nullptr) {}
};

class Solution {
public:
    Node* connect(Node* root) {
        Node* pre = root;
        Node* nextPre = nullptr;
        Node* prev = nullptr;
        
        while (pre) {
            while (pre) {
                if (pre->left) {
                    if (prev) prev->next = pre->left;
                    else nextPre = pre->left;
                    prev = pre->left;
                }
                if (pre->right) {
                    if (prev) prev->next = pre->right;
                    else nextPre = pre->right;
                    prev = pre->right;
                }
                pre = pre->next;
            }
            pre = nextPre;
            nextPre = nullptr;
            prev = nullptr;
        }
        return root;
    }
};

// Test helper
void printTree(Node* root) {
    cout << "[";
    if (!root) { cout << "]" << endl; return; }
    queue q;
    q.push(root);
    q.push(nullptr);
    while (q.size() > 1) {
        Node* curr = q.front(); q.pop();
        if (!curr) {
            q.push(nullptr);
            cout << "#, ";
        } else {
            cout << curr->val << ", ";
            if (curr->left) q.push(curr->left);
            if (curr->right) q.push(curr->right);
        }
    }
    cout << "]" << endl;
}

int main() {
    Node* root = new Node(1,
        new Node(2, new Node(4), new Node(5)),
        new Node(3, new Node(6), new Node(7))
    );
    Solution ob;
    root = ob.connect(root);
    printTree(root); // [1, #, 2, 3, #, 4, 5, 6, 7, #]
    return 0;
}

อินพุต / เอาต์พุต

Input: [1,2,3,4,5,6,7]

Output: [1, #, 2, 3, #, 4, 5, 6, 7, #]

ความซับซ้อน

• Time: O(n)
• Space: O(1)

ความต่างกับ Node II

โค้ดเหมือนกันทุกประการ แต่มั่นใจได้ว่า pre->left และ pre->right จะมีคู่กันเสมอ (Complete Tree) ทำให้ logic สะดวกกว่าเล็กน้อย