난이도 - Hard
Intuition
이 문제는 DFS가 접근하기 좋은 알고리즘이다. 왜냐하면 맨 왼쪽부터 오른쪽으로 순서에 맞게 값들을 정리해야하기 때문이다. 하지만 사실 HashTable을 통해 col, row를 기록해 놓는다면, BFS로도 풀수는 있다. 나는 여기에서 DFS를 사용했다.
1. root가 None이면 []를 반환한다.
2. columnTable를 defaultdict(list)로 초기화한다. 따라서 우리는 매 col마다 그에 맞는 (row, node.val)값을 집어넣을 것이다. 또한 min_col, max_col을 0으로 설정해놓고 tracking함으로써 우리는 나중에 columnTable를 for문을 통해 접근할 수 있다.
3. dfs를 돌린다. 먼저 현재 node과 row, col을 알고 있으므로, columnTable[col]에 (row, node.val)을 append한다. 그리고 다음 dfs를 왼쪽, 오른쪽 노드에 다시 돌린다.
4. 이제 우리는 완성된 hash table을 가지고 있다. min_col, max_col를 사용해 for문을 돌리면서 columnTable[col]를 sorted하면 row와 val값에 따라 자동으로 sorting이 되므로 이를 하나씩 답에 넣으면 된다.
Code
# 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]]:
if root is None:
return []
columnTable = defaultdict(list)
min_col = max_col = 0
def dfs(node, row, col):
if not node:
return
nonlocal min_col, max_col
columnTable[col].append((row, node.val))
min_col = min(min_col, col)
max_col = max(max_col, col)
dfs(node.left, row+1, col-1)
dfs(node.right, row+1, col+1)
dfs(root, 0, 0)
ans = []
for col in range(min_col, max_col+1):
ans.append([val for row, val in sorted(columnTable[col])])
return ansComplexity
Time Complexity: O(nlog(n/k)) 여기서 k는 column의 개수(tree의 width)이다. 처음에 DFS를 함으로써 O(n)이 소요된다. 그 다음, 우리는 hash map을 돌면서 sorting을 해야하므로, 여기서 O(nlog(n/k))가 소요된다. 그리고 마지막에 ans에 집어넣을때 O(n)이 소요된다. 결과적으로 전체 시간복잡도는 O(nlog(n/k))가 된다.
Space Complexity: O(n) BFS와 DFS접근법은 O(n)의 공간복잡도를 가진다.