314. Binary Tree Vertical Order Traversal

링크 - https://leetcode.com/problems/binary-tree-vertical-order-traversal/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

1) Breadth-First Search (BFS)

이 문제에서는 모든 노드들이 level by level로 접근되어 저장되어야 하므로 BFS가 가장 적합한 알고리즘이라고 생각이 들 것이다. 

그리고 horizontal order는 hash table로 저장하여 나중에 순서대로 접근하면 모든 노드들이 left-to-right, up-to-bottom형태로 저장이 될 것이다.

# 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 verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        dic = defaultdict(list)
        min_col = float('inf')

        stack = deque()
        stack.append((root, 0))
        while stack:
            node, col = stack.popleft()
            if not node:
                continue

            min_col = min(min_col, col)
            dic[col].append(node.val)

            stack.append((node.left, col - 1))
            stack.append((node.right, col + 1))

        ans = []
        col = min_col
        while min_col in dic.keys():
            ans.append(dic[min_col])
            min_col += 1

        return ans

Time Complexity: O(n) 먼저 우리는 BFS로 O(n)을 소모한다. 그 다음 hash table에서 key값에 맞는 list들을 저장하므로 O(n)이 소모된다.

Space Complexity: O(n)

2) Depth-First Search (DFS)

DFS로도 풀 수 있기는 하다. 하지만 우리는 level값도 따로 저장해야하고 나중에 sorting을 해줘야 하므로 그다지 효율적인 알고리즘은 아니다.