[leetcode] 104. Maximum Depth of Binary Tree Python

 

최근에 트리 이론과 재귀를 제대로 이해하고 이제 직접 코딩으로 구현을 해보는 연습을 하고 있는 중이다.

그 중에 내가 풀어놓고 답인지 아닌지 햇갈렸던 문제 중 하나가 위의 문제였다.

일단 답은 다음과 같이 간단하게(?) 구현이 가능하다.

# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        else:
            return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

 

일단 if not root 부분은 base 코드, 즉 재귀를 끝내기 위한 코드인 것은 금방 추론이 가능하다.

문제는 return 부분이다.

 

최대한 쉽게 말로 풀이를 해보자면 이렇게 된다.

1. 우선 3으로 root가 시작된다
2. 3의 root.left는 9가 된다.
3. self.maxDepth(root.left)에는 9가 들어가는 것이므로, maxDepth(self, 9)가 된다.
4. 9가 들어오면 일단 다시 else문으로 가게 된다.
5. 9일 때, self.maxDepth(root.left)와 self.maxDepth(root.right)는 둘 다 null이므로, return max(0, 0)+1이 되므로 return 1이 된다.
6. 따라서 이제 9일 때 1이 나오기 때문에 재귀한 것을 타고 올라가면, 맨 처음 root가 3이었을 때, max(1, self.maxDepth(root.right))+1인 것을 알 수 있다.
7. 이제 self.maxDepth(root.right)도 똑같이 해주면 (이 경우에는 20이 들어가고, 들어간 후 각각 15, 7이 나올 것이다)), 결국 root가 3이었을 때, return self.maxDepth(1,2)+1이 된다.
8. 따라서, 결론적으로는 return 2+1 즉, return 3이 나온다.

재귀는 계속 풀어봐야하는 것을 느낀다.

과거에 여러 번 코딩테스트 시도를 실패했던 첫 번째 관문 중 하나가 나에게는 항상 재귀였다 (이를 활용한 트리도...).

계속 여러 문제를 이번에는 끈덕지게 풀어보고자 한다.