สมมติว่าเรามีต้นไม้ไบนารี เราต้องท่องต้นไม้นี้แบบ Level Order Traversal (ท่องทีละระดับจากบนลงล่าง ซ้ายไปขวา)
เช่น ต้นไม้ที่มีโครงสร้างดังภาพ ลำดับการท่องจะเป็น [1, 2, 3, 5, 4]
ขั้นตอนการแก้ปัญหา
- สร้างคิว (queue) เก็บโหนด
- ใส่รูทเข้าไปในคิว
- วนลูปจนคิวว่าง:
- นำโหนดหน้าคิวออก (front)
- พิมพ์/เก็บค่าของโหนดนั้น
- ถ้ามีลูกซ้าย ใส่ลูกซ้ายเข้าคิว
- ถ้ามีลูกขวา ใส่ลูกขวาเข้าคิว
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v) {
cout << "[";
for (int i = 0; i < v.size(); i++) {
cout << v[i] << ", ";
}
cout << "]" << endl;
}
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) {
val = data;
left = right = NULL;
}
};
class Solution {
public:
vector<int> solve(TreeNode* root) {
if (!root) return {};
vector<int> ret;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
ret.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
return ret;
}
};
int main() {
TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->right = new TreeNode(5);
root->right->right = new TreeNode(4);
Solution ob;
print_vector(ob.solve(root));
}
อินพุต
TreeNode *root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->right = new TreeNode(5); root->right->right = new TreeNode(4);
เอาต์พุต
[1, 2, 3, 5, 4, ]
