[트리 순회 (Tree Traversal)] LC #589 N-ary Tree Preorder Traversal

문제 설명

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)

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]

Constraints:

Follow up: Recursive solution is trivial, could you do it iteratively?


문제 링크: https://leetcode.com/problems/n-ary-tree-preorder-traversal/

1. 문제의 핵심: 전위 순회(Preorder Traversal)의 이해

트리 순회는 알고리즘의 기본 중의 기본입니다. 전위 순회는 "루트(자기 자신) → 자식들" 순서로 노드를 방문하는 것을 의미합니다. 이진 트리에서는 "루트 → 왼쪽 → 오른쪽" 순서였지만, 자식이 여러 개인 N-ary 트리에서는 "루트 → 첫째 자식 서브트리 → 둘째 자식 서브트리 → ..." 순서로 방문하게 됩니다.

핵심 아이디어: 1. 현재 노드를 먼저 처리(방문)한다. 2. 그 다음, 자식 노드들을 순서대로 재귀적으로 방문한다.

2. 해결 전략

문제의 Follow-up에서 재귀적 풀이와 반복적 풀이를 모두 요구하고 있습니다.

방법 1: 재귀(Recursion)를 이용한 풀이

  1. 결과를 담을 리스트를 생성합니다.
  2. 재귀적으로 동작할 헬퍼(helper) 함수를 만듭니다. 이 함수는 현재 노드와 결과 리스트를 인자로 받습니다.
  3. 헬퍼 함수 내부 로직:
    • 현재 노드가 `null`이면 즉시 종료합니다.
    • 현재 노드의 값을 결과 리스트에 추가합니다. (루트 먼저 처리)
    • 현재 노드의 모든 자식(children)에 대해 재귀적으로 헬퍼 함수를 호출합니다.

방법 2: 반복(Iteration)과 스택(Stack)을 이용한 풀이

  1. 결과를 담을 리스트와 노드를 담을 스택을 생성합니다.
  2. 루트 노드가 `null`이 아니면 스택에 추가합니다.
  3. 스택이 빌 때까지 반복합니다.
    • 스택에서 노드를 하나 꺼내(pop) 현재 노드로 지정하고, 그 값을 결과 리스트에 추가합니다.
    • 현재 노드의 자식들을 역순(오른쪽부터 왼쪽으로)으로 스택에 넣습니다.
  4. 결과 리스트를 반환합니다.

3. Java 코드 구현

재귀적 풀이 (Recursive)

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> result = new ArrayList<>();
        traverse(root, result);
        return result;
    }

    private void traverse(Node node, List<Integer> list) {
        if (node == null) {
            return;
        }
        // 1. 루트 노드 먼저 방문
        list.add(node.val);
        // 2. 자식 노드들을 순서대로 방문
        for (Node child : node.children) {
            traverse(child, list);
        }
    }
}

반복적 풀이 (Iterative)

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Stack<Node> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Node current = stack.pop();
            result.add(current.val);

            // 자식들을 역순으로 스택에 넣어야 왼쪽부터 처리됨 (LIFO)
            Collections.reverse(current.children);
            for (Node child : current.children) {
                stack.push(child);
            }
        }
        return result;
    }
}

💡 코드 세부 포인트