589. N-ary Tree Preorder Traversal
전위 순회(preorder)는 다음과 같은 방법으로 진행한다.
- 노드를 방문한다.
- 왼쪽 서브 트리를 전위 순회한다.
- 오른쪽 서브 트리를 전위 순회한다.
전위 순회는 깊이 우선 순회(depth-first traversal)라고도 한다.
문제에서는 쉬운 재귀탐색 외에 반복문으로 해결하라고 한다.
Input: root = [1,null,3,2,4,null,5,6]
Output: [1,3,5,6,2,4]
위 테스트 케이스로 전위 순회를 하면 [1,3,5,6,2,4]
결과를 얻을 수 있다. 이진트리일 경우 left
, right
로 각각 재귀하면 되지만 문제에서는 N개의 자식노드가 올 수 있기 때문에 반복문을 사용한다. 스택을 사용하기 때문에 node.children
을 담을 때 역순으로 담아준다.
/**
* @param {Node|null} root
* @return {number[]}
*/
var preorder = function(root, result = []) {
if (root === null) return result;
result.push(root.val);
for (let child of root.children) {
preorder(child, result);
}
return result;
};
/**
* @param {Node|null} root
* @return {number[]}
*/
var preorder = function(root) {
const result = [];
if (root === null) return result;
const stack = [root];
while (stack.length > 0) {
const node = stack.pop();
result.push(node.val);
for (let i = node.children.length - 1; i >= 0; i--) {
stack.push(node.children[i]);
}
}
return result;
};