[python3] 987. Vertical Order Traversal of a Binary Tree

풀이 일자: 22.09.04

난이도: [Hard]

분류: [Hash Table/ DFS/ BFS/Binary Tree]

문제 내용

root(0,0)부터 아래로 내려가면서 왼쪽 노드는 +1 -1 오른쪽 노드는 +1 +1을 좌표에 더하여 y좌표가 같은 것끼리 묶어서 값을 리턴하는 문제였다.

 

문제 해결 흐름

1. 일단 이것도 트리 순회를 하면서 값을 정리하는 것이므로 트리 순회 알고리즘이 필요하겠다.

→ 간편한 DFS 방식을 사용해볼까?

2. 트리의 크기를 최대 최소로 알아볼까?

→ 현재 가질 수 있는 맨 아래 최대 최소 좌표는 (9,-9) ~ (9,9)이다. 그 이유는 최대 1000개의 노드가 있으므로 2^n으로 등비수열의 합을 게산해보면 0 ~ 9 level까지 가능하다는 것을 확인할 수 있기 때문이다.

3. 같은 y값을 가지고 있다면 top-bottom > 크기 순으로 처리를 해야하겠네.

→ DFS의 중위순회를 채택할 것이기 때문에 top-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 verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        maxLevel = floor(math.log(1001)/math.log(2))        # 1*(2^n - 1) / (2-1) = 1000
        maxLength = (maxLevel + 1) * 2
        
        ans = [[] for i in range(maxLength)]
        history = dict()
        
        dq = deque()            # 순회를 위한 deque생성
        dq.append((root, 0, 0))
        minY, maxY = inf, - inf
        
        while dq:   # 순회시작
            node, level, y = dq.popleft()
            minY = y if y < minY else minY
            maxY = y if y > maxY else maxY
            
            Y = y + 9      # 보정..
            
            ans[Y].append(node.val) # 일단 해당하는 위치에 넣기
            
            index = Y*10 + level # dictionary 사용을 위한 임의의 key설정.
            
            if index in history.keys():  # 만약 그 위치 원소가 있다면 
                history[index] += 1      # 일단 증가시키고 
                ans[Y][-1*history[index]:] = sorted(ans[Y][-1*history[index]:]) # 그 수만큼 정렬시킴.
            else:
                history[index] = 1
            
            if node.left:
                dq.append((node.left, level + 1, y - 1))
            if node.right:
                dq.append((node.right, level + 1, y + 1))
        ans = ans[minY + 9: maxY + 9 + 1]
        return ans

신기하게도 실행할 때마다 런타임시간과 메모리사용량이 변동이 심했다. 따라서 별로 좋지 못한 알고리즘을 짠 것으로 보인다.

 

다른 해결 방식

1. 풀다보니 BFS 방식이 해당 문제에 더 잘 어울릴 것이라는 생각이 들었다. 

→  DFS의 경우 top-bottom 순서에 대해서는 신경을 쓰지 않아도 되나 같은 level을 확인하는 것이 아니라서 같은 좌표가 또 나오는지 확인을 위해 해당 정보를 계속 가지고 있어야 한다는 단점이 많이 드러났다.

→ BFS 방식의 경우 level별로 확인하는 것이기 때문에 DFS와 같이 top-bottom 순서에 대해 신경쓰지 않아도 되며 같은 좌표는 같은 level에서만 나오기 때문에 해당 level이 끝날때까지만 해당 정보를 가지고 있으면 된다.

 

 

 

 

문제 링크

https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/