การท่องต้นไม้ N-ary แบบ Level Order ใน C++

การท่องต้นไม้ N-ary แบบ Level Order (N-ary Tree Level Order Traversal)

ให้ต้นไม้ N-ary (โหนดแต่ละตัวมีลูกได้หลายตัว) ทำ level order traversal คืนค่าเป็นลิสต์ของลิสต์ค่าแต่ละระดับ

ตัวอย่าง: [1,null,3,2,4,null,5,6] → [[1],[3,2,4],[5,6]]

ขั้นตอนการแก้ปัญหา (BFS)

1. สร้าง ans (vector of vector)
2. ถ้า root null คืนค่า ans ว่าง
3. คิว q ใส่ root
4. วนในขณะที่คิวไม่ว่าง:
   • sz = q.size()
   • สร้าง temp เก็บค่าระดับนี้
   • วน sz รอบ:
     • นำ curr ออกจากคิว
     • เพิ่ม curr.val เข้า temp
     • ใส่ลูกทั้งหมดของ curr เข้าคิว
   • เพิ่ม temp เข้า ans
5. คืนค่า ans

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

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(); q.pop();
                temp.push_back(curr->val);
                for (Node* child : curr->children) q.push(child);
            }
            ans.push_back(temp);
        }
        return ans;
    }
};

อินพุทและเอาต์พุทตัวอย่าง

Input: [1,null,3,2,4,null,5,6]

Output: [[1],[3,2,4],[5,6]]