589. N-ary Tree Preorder Traversal

589. N-ary Tree Preorder Traversal

문제

전위 순회(preorder)는 다음과 같은 방법으로 진행한다.

1. 노드를 방문한다.
2. 왼쪽 서브 트리를 전위 순회한다.
3. 오른쪽 서브 트리를 전위 순회한다.
   전위 순회는 깊이 우선 순회(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;
};

stack을 이용한 반복문

/**
 * @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;
};

출처

• 트리 순회 | wiki