Kết nối con trỏ Next Right II trong C++

Cho cây nhị phân không hoàn chỉnh, mỗi nút có con trỏ next trỏ sang nút bên phải cùng cấp. Kết nối tất cả con trỏ next (NULL nếu không có nút bên phải).

Thuật toán giải quyết (Duyệt theo cấp không dùng queue)

Sử dụng con trỏ pre duyệt cấp hiện tại, nextPre và prev xây dựng cấp tiếp theo.

1. pre = root, nextPre = prev = nullptr.
2. Trong khi pre không null:
   • Duyệt linked list cấp hiện tại qua pre:
     • Nếu pre->left: nối vào prev->next (hoặc gán nextPre), cập nhật prev.
     • Nếu pre->right: tương tự.
     • pre = pre->next.
   • Chuyển sang cấp tiếp theo: pre = nextPre, reset nextPre = prev = nullptr.
3. Trả về root.

Ví dụ minh họa (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 v) : val(v), left(nullptr), right(nullptr), next(nullptr) {}
    Node(int v, Node* l, Node* r) : val(v), left(l), right(r), next(nullptr) {}
};

class Solution {
public:
    Node* connect(Node* root) {
        Node *pre = root, *nextPre = nullptr, *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 = prev = nullptr;
        }
        return root;
    }
};

Đầu vào

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

Đầu ra

[1, #, 2, 3, #, 4, 5, 7, #, ]