N-ary Tree Preorder Traversal ใน C++

แนวคิด

สมมติว่ามี N-ary tree ให้หา preorder traversal ของโหนดต่างๆ

เช่น ถ้าอินพุตเป็น:

ผลลัพธ์จะเป็น [1,3,5,6,2,4]

วิธีแก้:

• กำหนดอาร์เรย์ ans
• กำหนดเมธอด preorder() รับ root
• ถ้า root เป็น null: คืนค่ารายการว่าง
• แทรกค่าของ root ลงท้าย ans
• สำหรับทุก child i ใน children array ของ root: preorder(i)
• คืนค่า ans

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v) {
    cout << "[";
    for(int i = 0; i<v.size(); i++) {
        cout << v[i] << ", ";
    }
    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<int> ans;
    vector<int> preorder(Node* root) {
        if (!root) return {};
        ans.emplace_back(root->val);
        for (auto i : root->children)
            preorder(i);
        return ans;
    }
};
main() {
    Solution ob;
    Node *node5 = new Node(5), *node6 = new Node(6);
    vector<Node*> child_of_3 = {node5, node6};
    Node* node3 = new Node(3, child_of_3);
    Node *node2 = new Node(2), *node4 = new Node(4);
    vector<Node*> child_of_1 = {node3, node2, node4};
    Node *node1 = new Node(1, child_of_1);
    print_vector(ob.preorder(node1));
}

อินพุต

Node *node5 = new Node(5), *node6 = new Node(6); vector<Node*> child_of_3 = {node5, node6}; Node* node3 = new Node(3, child_of_3); Node *node2 = new Node(2), *node4 = new Node(4); vector<Node*> child_of_1 = {node3, node2, node4}; Node *node1 = new Node(1, child_of_1);

เอาต์พุต

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