Duyệt cấp độ cây N-ary trong C++

Cho cây N-ary, trả về duyệt cấp độ (level order traversal) các giá trị nút. Đầu vào tuần tự hóa theo cấp độ, các nhóm con cách nhau bằng null. Ví dụ: [1,null,3,2,4,null,5,6] → [[1],[3,2,4],[5,6]].

Giải thuật

• Ma trận kết quả ans.
• Nếu root == null trả về ans.
• Hàng đợi q, đưa root vào.
• Khi q không rỗng:
  • size := q.size().
  • Mảng tạm temp.
  • Khi size-- > 0:
    • curr := q.front(), đưa curr->val vào temp, xóa khỏi hàng đợi.
    • Duyệt các con của curr đưa vào q.
  • Đưa temp vào ans.
• Trả về ans.

Ví dụ mã 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;
    }
};

Đầu vào

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

Đầu ra

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