[LeetCode] 314. Binary Tree Vertical Order Traversal

314. Binary Tree Vertical Order Traversal

Medium

Given the root of a binary tree, return the vertical order traversal of its nodes' values. (i.e., from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

 

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

Example 2:

Input: root = [3,9,8,4,0,1,7]
Output: [[4],[9],[3,0,1],[8],[7]]

Example 3:

Input: root = [3,9,8,4,0,1,7,null,null,null,2,5]
Output: [[4],[9,5],[3,0,1],[8,2],[7]]

 

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

---

문제 풀이

문제 접근

1. 바이너리 트리 문제이다, 트리 문제는 탐색할 수 있는 방법들이 재귀, 이진탐색, 스택, DFS, BFS 등이 있다. 
2. 논외로 Height 별로 노드를 저장하는 문제는 BFS를 사용해서 풀어야한다.
3. 거기서 힌트를 얻어서 노드를 저장할때, index를 매겨 저장하자.
4. index로 저장할때는 딕셔너리(해쉬맵)을 사용해서 저장한다.
5. 그리고 출력 마무리는 정렬로 한다.

풀이

1. 구해야하는 답을 쉽게 생각해보면, 출발 지점에서 Columns 별로 저장해야한다. 
   Height 별로 노드들을 저장하는 문제와 유사하다.
2. 재귀, DFS로는 원하는 답을 얻기 힘들어 보였다.
3. Pre-order, In-order, Past-order 순회들 중 어느 것도 맨위에 있는 노드를 리스트에 먼저 저장할 수 없어 보인다.
   예시: 아래 그림을 일반 재귀로 탐색해서 얻는다고 하면 8보다 2가 먼저 리스트에 저장된다.
   [[4],[9,5],[3,0,1],[8,2],[7]] 이 아니라 [[4],[9,5],[3,0,1],[2,8],[7]] 이 될 것이다.
   
4. 위에서 부터 차례대로 노드를 방문하는 방법은 BFS 밖에 없다. 
5. BFS를 활용하여 노드들을 방문하고, 가운데 시작 노드부터 index를 사용해 -1, +1 하여 해쉬맵(딕셔너리)에 저장하여 리스트를 만들자.
6. 제한 조건에서 0개의 노드도 있을 수 있음을 주의한다.
7. 리스트 딕셔너리를 만들어 답을 리스트로 추가해주고, 마지막에 출력할때 key로 정렬을 한다. 

소스 코드

# 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]]:
        if not root:
            return []
        hashmap = defaultdict(list)
        q = collections.deque()
        q.append((root, 100))
        while q:
            curr, idx = q.popleft()
            hashmap[idx].append(curr.val)
            if curr.left:
                q.append((curr.left, idx - 1))
            if curr.right:
                q.append((curr.right, idx + 1))
        res = dict(sorted(hashmap.items()))
        return res.values()