Populating Next Right Pointers in Each Node II ใน C++: เชื่อม Next Pointer ต้นไม้ไบนารีทั่วไป

โจทย์

ต้นไม้ไบนารีทั่วไป (ไม่จำเป็นต้อง complete) แต่ละโหนดมี left, right, next ตั้งค่า next ชี้ไปโหนดขวาในระดับเดียวกัน (NULL ถ้าไม่มี)

แนวคิด: Level Order Traversal ไม่ใช้ Queue (O(1) Space)

ใช้ pointer pre เดินระดับปัจจุบัน nextPre จดโหนดแรกของระดับถัดไป prev จดโหนดล่าสุดในระดับถัดไป

ขั้นตอน

1. pre = root, nextPre = nullptr, prev = nullptr
2. while pre:
   • while pre (เดินระดับปัจจุบัน):
     • ถ้า pre->left: เชื่อม prev->next = pre->left (หรือ nextPre = pre->left ถ้าเป็นตัวแรก) → prev = pre->left
     • ถ้า pre->right: เชื่อม prev->next = pre->right (หรือ nextPre = pre->right) → prev = pre->right
     • pre = pre->next
   • pre = nextPre; nextPre = prev = nullptr (ขึ้นระดับถัดไป)
3. return root

ตัวอย่างโค้ด 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) : val(_val), 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;
    }
};

// Helper สำหรับทดสอบ (print tree level by level)
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, nullptr, new Node(7))
    );
    Solution ob;
    root = ob.connect(root);
    printTree(root); // [1, #, 2, 3, #, 4, 5, 7, #, ]
    return 0;
}

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

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

Output: [1, #, 2, 3, #, 4, 5, 7, #] (# = null/level separator)

ความซับซ้อน

• Time: O(n) - เยี่ยมแต่ละโหนด 1 ครั้ง
• Space: O(1) - ไม่ใช้ queue/recursion