최근 풀었던 문제들 중 처음 접했을 때 잘 못풀었어서 Tree를 순회하는 방법을 공부하고 다시 풀어보았다.
문제를 처음 접하고 든 생각은 최대깊이를 구해야 하기 때문에 모든 node를 순회하는 방법을 사용해야 한다고 생각했다. 그래서 DFS와 BFS 중 하나를 선택해야 한다고 생각했고 깊이니까 DFS를 사용해야겠다고 근거 없이 결정하고 문제를 접근했다. DFS는 스택을 써야 한다 정도의 개념만 가지고 풀었어서 어떻게 구현할 수 있을까 고민을 하다가 아래 코드를 작성했다.
def maxDepth(self, root: Optional[TreeNode]) -> int:
if root == None:
return 0
pointer = root
result = 1
stack = []
already = []
while True:
stack.append(pointer)
#현재 pointer가 가리키는 node를 stack에 추가
result = max(result, len(stack))
#stack의 최대 길이를 result에 지속적으로 저장
if pointer.left != None and pointer.left not in already:
pointer = pointer.left
#위 조건을 만족할 경우 pointer이 left leaf node로 이동
elif pointer.right != None and pointer.right not in already:
pointer = pointer.right
#위 조건을 만족할 경우 pointer이 right leaf node로 이동
else:
if pointer == root:
break
#종료조건: root에서 더이상 갈 수 없을 때 loop 종료
stack = []
already.append(pointer)
pointer = root
#최하위의 leaf node일 때 already에 그 node를 기록
#stack 초기화 및 pointer 초기화
return result테스트 케이스를 통과해 제출을 눌렀으나 Time Limit Exceeded가 떴다. 내가 생각하는 이 에러가 뜬 가장 큰 이유는 root에서 모든 node까지 가는 길을 전부 센 것이 문제라고 생각한다. 최하위의 node를 찍었으면 그 과정에 있던 경로는 굳이 가지 않고 넘겼어야 했다. 두 번째 이유는 Tree 공부를 안한 나
이후 DFS, BFS를 자세히 알아보고 나서는 생각이 바뀌었다. DFS로 구현해도 모든 node를 순회할 수 있지만 depth를 계산하기에는 BFS가 더 간편하다는 결론을 내려 BFS를 사용해 구현하였다.
def maxDepth(self, root: Optional[TreeNode]) -> int:
if root == None:
return 0
queue = [root]
depth = 0
while queue:
depth += 1
#한 층이 늘어날 때 마다 depth 추가
for i in range(len(queue)):
node = queue.pop(0)
if node.left != None:
queue.append(node.left)
if node.right != None:
queue.append(node.right)
#한 층의 모든 node를 조회해 그 node의 leaf node들을 queue에 추가
#for loop가 끝나면 queue에는 다음 층의 모든 leaf node들이 들어감
return depth보기에도 더 편하고 직관적인 코드로 변했다. 이렇게 작성한 결과 Success를 받아냈다.
그러나 그다지 빠른 방법이 아니었기 때문에 추가적으로 최적화를 시킬 수 있을 것이다. 최적화 방법으로는 list.pop(0)이 O(N)이기 때문에 O(1)을 할 수 있는 deque를 import해서 사용하는 방법이다. 실제로 28ms가 걸린 경우의 코드는 다음과 같았다. (상위 5% 미만)
문제를 쩔쩔매고 푸는데 Easy라는 난이도가 계속 눈 앞을 어른거렸다. 내가 아직 많이 부족하다는 생각이 들었다. 공부 열심히 하자.
