Leetcode - 589. N-ary Tree Preorder Traversal

문제

바이너리 트리가 아니라, 자식이 여러개인 트리를 preorder 순회하라.

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

해결

사실 바이너리 트리랑 순회순서가 동일하다. 루트노드를 저장한뒤, 바이너리 트리가 left/right를 재귀로 순회했다면, 여기서는 child1,child2...childN 순차적으로 재귀를 호출하면 된다.

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}
    ......
};
*/
class Solution {
    void dfs_preorder(Node *root, vector<int> &ret) {
        if (root == NULL)
            return;
        ret.push_back(root->val);
        for (auto n: root->children) {
            dfs_preorder(n, ret);
        }
    }
public:
    vector<int> preorder(Node* root) {
        vector<int> ret;
        dfs_preorder(root, ret);
        return ret;
    }
};