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

Cho cây nhị phân hoàn chỉnh (complete binary tree), kết nối con trỏ next của mỗi nút sang nút bên phải cùng cấp.

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

Tương tự bài II nhưng tận dụng tính chất cây hoàn chỉnh: mọi nút đều có 2 con hoặc 0 con.

1. pre = root, nextPre = prev = nullptr.
2. Trong khi pre:
   • Duyệt linked list cấp hiện tại:
     • Nối pre->left và pre->right vào cấp dưới qua prev/nextPre.
     • pre = pre->next.
   • pre = nextPre, reset nextPre = prev = nullptr.

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, 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,6,7]

Đầu ra

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