문제
Approach 1. DFS recursively
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root: [1]
return 0
if not root.left and not root.right: [2]
return 1
if not root.left: [3]
return self.minDepth(root.right) + 1
if not root.right: [4]
return self.minDepth(root.left) + 1
return min(self.minDepth(root.right),\
self.minDepth(root.left)) + 1 [5]위의 방식은 내가 처음에 푼 방식이다. DFS는 iterative 하게 푸는 방식, recursive 하게 푸는 방식 두가지로 나눌 수 있다. iterative 하게 풀면 BFS를 적용하는 방식과 비슷한데, 대신 queue를 쓸 것을 stack으로 대체한다는 점이 있다.
그러하여 recursive 한 코드를 만들어보았다.
[1] 어느 recursion이나 base case가 있어야하는법. 첫번째 base case는 최상단 node인 root가 None인 경우이다. 이때 0을 리턴한다.
[2] 두번째 base case는 root의 양옆이 None인 경우이다. 그렇다면 root 밖에 없는 tree이므로 depth는 1이 된다. 1을 리턴한다.
[3] 이제 recursion 시작이다. 만약 root의 left는 None이고, root의 right는 None이 아니라면 minDepth을 부른다.
minDepth이 리턴하는 depth 값에 1을 더해준다.
1을 더해주지 않는다면 그 전 node까지의 깊이만 계산되기 때문에, 반드시 1을 더해주어 값을 업데이트 해준다.
[4] root의 right는 None이고, root의 left는 None이 아니라면, minDepth을 부르고 minDepth이 리턴하는 depth 값에 1을 더해준다.
[5] root의 left와 right가 둘다 있는 경우, 둘중에 더 값이 작은 것을 골라서 1을 더해준다.
예시에 있는 input으로 적절한 곳에 root.val와 condition을 프린트를 해보았다.
input: [3,9,20,null,null,15,7]
stdout:
=======================================
root is 3
root has both children
=======================================
root is 20
root has both children
=======================================
root is 7
root has no children
=======================================
root is 15
root has no children
=======================================
root is 9
root has no children
예상했던대로 3, 20, 7, 15, 9 순으로 탐색하는 것을 볼 수 있다. 최하단인 7에 먼저 도달하였다.
Approach 2. BFS
class Solution:
def minDepth(self, root:TreeNode) -> int:
if not root: [3]
return 0
q = collections.deque() [1]
q.append((root,1)) [2]
while q: [4]
node, depth = q.popleft() [5]
if not node.left and not node.right: [6]
return depth
if node.left: [7]
q.append((node.left, depth+1))
if node.right: [8]
q.append((node.right, depth+1))[1] tree를 저장하기 위해서 collection이란 모듈에서 deque를 가져온다.
[2] 처음 tree와 depth 1을 저장한다. root가 한개만 있으면 depth는 1일 것이기 때문이다. root가 None이라면 맨 처음 줄 [3]에서 걸려서 0을 리턴한다.
[4] q가 빈 값이 아닐때까지 while loop을 돌린다.
[5] 일단 q안에 저장되어있는 node와 depth을 popleft를 통해 가져온다.
[6] 만약 node의 left, right 모두가 None일때 (즉, node가 tree의 최하단일때) depth를 리턴한다
[7] 만약 node의 left만 있는 경우, (right는 None인 경우) q에 node의 left에 있는 subtree를 저장, 깊이는 +1을 해줌으로서 업데이트
[8][7]와 마찬가지로 node의 right만 있는 경우, right subtree 저장, 깊이 +1함으로서 업데이트
[6]일때 while loop에서 나와서 값을 리턴하도록 되어있다!
예시에 있는 input으로 적절한 곳에 root.val와 condition을 프린트를 해보았다.
input: [3,9,20,null,null,15,7]
stdout:
=================================
node is 3
depth: 1
=================================
node has left child
=================================
node has right child
=================================
node is 9
depth: 2
=================================
node has no children
비교
아래가 DFS, 위에가 BFS로 푼 결과이다.
걸리는 시간과 메모리를 보면 DFS가 더 오래 걸린다는 것을 알 수 있다. 그 이유는 이 문제가 maximum depth이 아니고 minimum depth을 구하는 것이기 때문이다. children이 더 이상 존재하지 않는 node를 찾고 root에서부터 node까지의 depth을 구하는 것이 목적이기 때문에 인접한 노드에서부터 탐색을 하는 것이 더 빠르다. 제일 최하단의 node까지 갈 이유가 없기 때문이다.
