589. N-ary Tree Preorder Traversal

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

팀 알고리즘 레포지토리 주소

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문제 출처

N-ary Tree Preorder Traversal - LeetCode

[문제 설명]

DFS로 왼쪽 깊은 순서부터 모든 요소 검색하기.

[처음 생각한 접근 방법]

그냥 단순한 DFS 구현문 같습니다. 단 스택에 넣을 때 왼쪽부터 넣으면

오른쪽부터 순서대로 나오게 되어서 FILO으로 인해 1,4,2,3,6,5 이런 식으로 나온다는 게 문제입니다.

이를 해결하기 위해 자식을 넣을 때 오른쪽부터 넣었습니다.

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> answer =  new ArrayList<>();
        Stack<Node> stack = new Stack<>();
        if (root == null) return answer;
        stack.push(root);

        while (!stack.isEmpty()) {
            Node temp = stack.pop();
            answer.add(temp.val);

            for (int i = temp.children.size() - 1; i >= 0; i--) {
                stack.push(temp.children.get(i));
            }
        }

        return answer;
    }
}