[Leetcode] 144. Binary Tree Preorder Traversal [Python, Easy]

 

[ 문제 풀이 ]

Preorder는 DFS(Depth First Search) 탐색 방법 중 하나이고, DFS는 스택으로 주로 구현한다.

Preorder는 3가지의 단계로 탐색을 한다.

1. Visit the Node

2. Traverse left

3. Traverse right

 

[ Root -> Left -> right ]

[ 루트 -> 왼쪽 노드 -> 오른쪽 노드 ]

순으로 순회를 한다.

 

한국어로 Preorder는 전위 순회, 이때 전은 먼저라는 뜻의 '前'

한글로 보면 바로 뭔지 체감이 안 가고 영어 단어를 보면 바로 이해가 간다.

영어로는 Preorder인데 Pre-order인 이유는 먼저 노드 방문부터 하고 그다음에 왼쪽, 오른쪽 탐색을 하기 때문

탐색보다 노드 방문을 먼저로 하기 때문이다.

 

 

< 설명 영상 >

 

[ 코드1.  재귀 사용 ]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        
        self.footage = []
        
        def Traversal(node):
            if not node: return []
            self.footage.append(node.val)
            Traversal(node.left)
            Traversal(node.right)
            
        Traversal(root)
        
        return self.footage

단순하게 Preorder 탐색 단계를 그대로 코드로 옮겨주면 된다.

노드가 있으면 현재 노드 방문할 때 node 값 추가 -> left node 탐색 -> right node 탐색

< 중요 포인트 >

1. 빈 Node일 시 return 

2. 당연한거지만 함수 안에 함수를 넣을 수 있다.

3. 재귀 함수

 

< 결과 >

 

 

[ 코드2. Stack으로 구현 ]

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []

        stack = [root]
        footage = []

        while stack:
            cur_node = stack.pop()
            if cur_node :
                footage.append(cur_node.val)
                stack.append(cur_node.right)
                stack.append(cur_node.left)
        return footage

마찬가지로 빈 Node 일 시에는 빈 배열 반환

stack이란 배열을 추가로 만들어서 node들을 추가해준다.

visit 한 노드는 탐색 기록 배열 footage에 추가하고 stack 배열에서 제거하고 left node 먼저 추가하고 right node를 추가한다.

 

< 결과 >

 

visit 하는 위치만 바꾸면 나머지 코드 그대로 Inorder, postorder도 풀 수 있다.

Binary Tree Preorder Traversal - LeetCode