[Iterative DFS] 144. Binary Tree Preorder Traversal

144. Binary Tree Preorder Traversal

 

재귀 방식

# 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: Optional[TreeNode]) -> List[int]:
        # 전위 순회(preorder traversal): 자신 -> 왼쪽 -> 오른쪽
        res = []

        def dfs(node):
            if not node:
                return  # 노드가 없으면 종료 (재귀 종료 조건)

            res.append(node.val)   # 1. 자기 자신 먼저 방문
            dfs(node.left)         # 2. 왼쪽 서브트리 방문
            dfs(node.right)        # 3. 오른쪽 서브트리 방문

        dfs(root)  # 루트 노드부터 시작
        return res  # 결과 리스트 반환

 

Iterative DFS

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

        res = []              # 결과를 담을 리스트
        stack = [root]        # 스택에 루트부터 시작

        while stack:
            node = stack.pop()      # 현재 노드 꺼냄
            res.append(node.val)    # 1. 자기 자신 먼저 방문

            # 전위 순회는 왼 -> 오 순서이지만,
            # 스택은 LIFO이므로 **오른쪽 먼저 push**, 그 다음 왼쪽 push 해야
            # 왼쪽이 먼저 pop되어 처리됨
            if node.right:
                stack.append(node.right)  # 2. 오른쪽 자식이 있으면 스택에 push
            if node.left:
                stack.append(node.left)   # 3. 왼쪽 자식이 있으면 그 다음에 push

        return res

 

https://youtu.be/afTpieEZXck