สมมติว่าเรามีต้นไม้ n-ary เราต้องส่งกลับการข้ามระดับของค่าโหนด การจัดลำดับอินพุต Nary-Tree จะแสดงในการข้ามผ่านเพื่อข้ามระดับ ที่นี่เด็กแต่ละกลุ่มจะถูกคั่นด้วยค่าว่าง (ดูตัวอย่าง) ต้นไม้ต่อไปนี้สามารถแสดงเป็น [1,null,3,2,4,null,5,6]
ผลลัพธ์จะเป็น [[1],[3,2,4],[5,6]]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
สร้างเมทริกซ์หนึ่งอัน
-
ถ้ารูทเป็นโมฆะ ให้คืนค่า ans
-
ทำหนึ่งคิว q และแทรกรูท
-
ในขณะที่ q ไม่ว่างเปล่า
-
size :=ขนาดของคิว
-
ทำให้หนึ่งอาร์เรย์ชั่วคราว
-
ในขณะที่ขนาดไม่ใช่ 0
-
curr :=องค์ประกอบแรกของ q
-
ใส่ค่าของ curr ลงใน temp
-
ลบองค์ประกอบออกจากคิว
-
สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของลูกของเคอร์
-
ใส่ลูกของcurr
-
-
ลดขนาดลง 1
-
-
ใส่อุณหภูมิลงใน ans
-
-
กลับมาอีกครั้ง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector < vector <int> > ans;
if(!root)return ans;
queue <Node*> q;
q.push(root);
while(!q.empty()){
int sz = q.size();
vector<int> temp;
while(sz--){
Node* curr = q.front();
temp.push_back(curr->val);
q.pop();
for(int i = 0; i < curr->children.size(); i++){
q.push(curr->children[i]);
}
}
ans.push_back(temp);
}
return ans;
}
};
main(){
Node *root = new Node(1);
Node *left_ch = new Node(3), *mid_ch = new Node(2), *right_ch = new Node(4);
left_ch->children.push_back(new Node(5));
left_ch->children.push_back(new Node(6));
root->children.push_back(left_ch);
root->children.push_back(mid_ch);
root->children.push_back(right_ch);
Solution ob;
print_vector(ob.levelOrder(root));
} อินพุต
[1,null,3,2,4,null,5,6]
ผลลัพธ์
[[1, ],[3, 2, 4, ],[5, 6, ],]
