[리트코드/leetcode/python] 589. N-ary Tree Preorder Traversal

이미지를 누르면 문제 링크를 보실 수 있습니다.

이미지를 누르면 문제 링크를 보실 수 있습니다.

주어진 트리배열을 보고 PreOrder 로 출력하는 문제입니다.

PreOrder은 아래와 같은 로직을 가지는데요, 부모를 먼저 출력하고, 자식 중에서 왼쪽->오른쪽 순으로 출력하는 로직을 가집니다.

preorder

PreOrder traversal 말고도 순회 종류에는 크게 4가지가 있습니다.

순회 종류 4가지 (노드 방문 순서에 따라)

• 전위 순회 (Preorder Traversal)
• 중위 순회 (Inorder Traversal)
• 후위 순회 (Postorder Traversal)
• 레벨 오더 순회(level-order Traversal)

전위 순위는 root -> left -> right

중위 순위는 left -> root -> right

후위 순위는 left -> right -> root

순으로 순회를 하며 root를 언제 출력하느냐가 화두죠. (레벨 오더는 말그대로 level 순으로 출력하는 것입니다)

 

이 문제는 PreOrder문제이므로, 재귀로 간단히 풀 수 있습니다.

먼저 코드를 보면서 살펴볼까요?

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def preorder(self, root: 'Node') -> List[int]:

        if not root:
            return []
        stack = [root.val]

        for node in root.children:
            stack.extend(self.preorder(node))
        
        return stack

if not root 는 더 이상 자식 노드가 없을 때 종료되는 탈출조건입니다.

맨 처음에는 stack에 root.val을 넣고 시작합니다. 가장 먼저 루트를 출력해야하니까요.

 

이제 현재 바라보고 있는 root노드의 children노드를 순회하기 시작합니다. 

각 children노드를 바라보면서 해당 children노드가 부모노드인 서브트리를 또 순회해야 하므로 preorder(node)로 재귀를 타면 됩니다.

이 때, 재귀문이므로, self를 반드시넣어줘야 하고, 기존 stack을 계속 연장해야하니까 extend 키워드를 사용해야 합니다.

직관적으로 이해가 될 것인데요, 어떤 traversal인지에 따라 재귀를 다르게 구성해야 할 수 있겠죠.

 

recursive한 방법 말고 iterative한 방법으로 코드를 고안해보면, 아래와 같습니다.

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

# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def preorder(self, root: 'Node') -> List[int]:

        # iterative
        if not root :
            return []
        
        stack = [root]
        answer = []

        while stack:
            cur_node = stack.pop()
            answer.append(cur_node.val)
            stack.extend(cur_node.children[::-1])
        
        return answer

stack에 root를 넣고 시작합니다. stack이 빌 때까지 계속 도는데, stack에서 가장 끝 값을 pop해주면서, answer 리스트에 넣어줍니다.

이 때, stack은 현재 바라보고 있는 노드의 자식노드들을 넣어줘야 하는데요, [::-1]을 하는 이유는 pop()은 맨 끝 값부터 제거하기 때문에, 부모 기준으로 좌측부터 순회하는 preorder traversal에서는 필수적인 작업입니다.

 

이상 N-ary Tree Preorder Traversal 문제를 정리해봤습니다.