바이너리 트리가 아니라, 자식이 여러개인 트리를 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;
}
};