N-ary Tree Preorder Traversal trong C++

Cho một cây N-ary (mỗi nút có thể có nhiều con), hãy thực hiện duyệt tiền thứ tự (preorder): thăm gốc trước, sau đó duyệt các con từ trái sang phải.

Ví dụ cây:

Kết quả preorder: [1, 3, 5, 6, 2, 4]

Giải thuật (Đệ quy)

1. Nếu nút gốc null, trả về mảng rỗng.
2. Thêm giá trị nút gốc vào kết quả.
3. Duyệt đệ quy từng con theo thứ tự.

Ví dụ triển khai 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<int> preorder(Node* root) {
        vector<int> ans;
        if (!root) return ans;
        ans.push_back(root->val);
        for (Node* child : root->children)
            preorder(child);
        return ans;
    }
};

// Helper để in vector
void print_vector(vector<int> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) cout << v[i] << (i+1<v.size()?", ":"");
    cout << "]" << endl;
}

int main() {
    Solution ob;
    Node *n5 = new Node(5), *n6 = new Node(6);
    vector<Node*> c3 = {n5, n6};
    Node *n3 = new Node(3, c3);
    Node *n2 = new Node(2), *n4 = new Node(4);
    vector<Node*> c1 = {n3, n2, n4};
    Node *n1 = new Node(1, c1);
    print_vector(ob.preorder(n1)); // [1, 3, 5, 6, 2, 4]
    return 0;
}

Đầu vào / Đầu ra

Input: Cây như hình (root = 1)
Output: [1, 3, 5, 6, 2, 4]