[Easy] 589. N-ary Tree Preorder Traversal

1. 문제

Given the root of an n-ary tree, return the preorder traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)

 

전위 순회하는 트리의 value 배열을 반환하는 문제이다.

 

2. 예시

Example 1:

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

Example 2:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]

 

3. 제약 조건

Constraints:

  • The number of nodes in the tree is in the range [0, 104].
  • 0 <= Node.val <= 104
  • The height of the n-ary tree is less than or equal to 1000.

 

4. 해결 과정

마침 이 문제를 반대로 수행하는 로직을 전에 leetCode에서 본 적이 있어 그 코드를 참고하고, 다른 분의 코드를 참고해보았다. 

그 때의 풀이는 queue로 해결하였는데 이번 문제는 stack으로 해결할 수 있었다. 

  • 트리의 노드를 다룰 stack 배열과 반환할 result 배열을 생성한다.
  • root가 falsy라면 빈 배열인 result를 반환한다.
  • stack의 첫번째 값으로 root를 넣는다.
  • stack의 길이가 0이 될 때까지 while문을 순회한다.
    • stack을 pop해서 현재 노드를 node 변수에 저장한다.
    • 이 node의 value값을 result에 저장한다.
    • for문을 돌면서 현재 node의 자식들을 stack에 저장한다.
  • val값이 저장된 result 배열을 반환한다.

5. 해결 코드

/**
 * // Definition for a Node.
 * function Node(val, children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node|null} root
 * @return {number[]}
 */
 
var preorder = function(root) {
    const stack = [];
    const result = [];
    
    if (!root) {
        return result;
    }
    
    stack.push(root);
    
    while(stack.length) {
        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;
};javascript

6. 참고 사이트

https://programmerplum.tistory.com/40?category=1022356 

 

[Medium] 116. Populating Next Right Pointers in Each Node

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/ Populating Next Right Pointers in Each Node - LeetCode Level up your coding skills and quickly land a job. This is the best..

programmerplum.tistory.com