বাইনারি ট্রির প্রতিটি নোডে next পয়েন্টার আছে। প্রতিটি লেভেলে নোডগুলোকে বাম থেকে ডানে `next` দিয়ে লিংক করুন। জেনারেল বাইনারি ট্রি (কমপ্লিট নয়)।
সমাধানের ধাপসমূহ
- লেভেল-অর্ডার ট্রাভার্সাল সিমুলেট করুন এক্সট্রা স্পেস ছাড়া।
pre= বর্তমান লেভেলের প্রথম নোড।nextPre= নেক্সট লেভেলের প্রথম নোড,prev= নেক্সট লেভেলে পূর্বের নোড।- বাম ও ডান চাইল্ড প্রসেস করুন,
prev->nextলিংক করুন। - লেভেল শেষে
pre = nextPre।
C++ উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int val;
Node *left, *right, *next;
Node(int v=0, Node* l=nullptr, Node* r=nullptr, Node* n=nullptr):val(v),left(l),right(r),next(n){}
};
class Solution {
public:
Node* connect(Node* root) {
Node* pre = root;
while (pre) {
Node* nextPre = nullptr;
Node* prev = nullptr;
for (Node* cur = pre; cur; cur = cur->next) {
if (cur->left) {
if (prev) prev->next = cur->left;
else nextPre = cur->left;
prev = cur->left;
}
if (cur->right) {
if (prev) prev->next = cur->right;
else nextPre = cur->right;
prev = cur->right;
}
}
pre = nextPre;
}
return root;
}
};
ইনপুট
[1,2,3,4,5,null,7]
আউটপুট
[1, #, 2, 3, #, 4, 5, 7, #, ]
