Leetcode #104 Maximum depth binary tree

문제 : Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

 

이번 문제는 파이썬으로 풀어 보겠다.

# 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:
        def dfs(root, depth):
            if not root: 
                return depth
            return max(dfs(root.left, depth + 1), dfs(root.right, depth + 1))
        
        return dfs(root, 0)

먼저, 깊이우선탐색(dfs) helper 메서드를 만들어 재귀적으로 호출하려고 한다. 

 

- 만약 루트노드가 None이면, 즉 트리가 비어있으면 맨 처음 maxDepth 호출시 인자로 주어졌던 dfs의 두번째 인자 '0'을 리턴한다.

- 그게 아니라면(비어있는 트리가 아니라면), dfs(root, 0)이 호출되어 maxDepth의 인자로 주어진 root과 처음 depth 0을 인자로 가지고 함수가 호출된다. 위의 첫번째 예시를 들어보자.

- 루트는 '3'이다. 즉, 첫번째 if문에서 false가 반환되므로  return max(dfs(root.left, depth + 1), dfs(root.right, depth + 1)) 가 재귀적으로 호출 될 것이다. 

- 이 재귀 호출문을 살펴보면 왼쪽 서브트리, 오른쪽 서브트리를 모두 깊이 우선탐색을 각각 진행 한 후, max를 사용해 최댓값(이 문제에서 구하고자 하는 최대깊이)를 리턴한다.

- 즉, 첫번째 예시의 경우엔 재귀문이 호출되면 왼쪽 서브트리의 루트 '3'에서 dfs가 호출 될 것이고, 여기서 또다시 재귀함수가 호출될 것이다(루트는 None이 아니라 '3'이므로). 그러면 또다시 3의 왼쪽, 오른쪽 서브트리에서 재귀문이 호출되는데, 여기서는 루트 '3'의 서브트리의 left, right모두가 None이므로 첫번째 if문에 걸려 depth == 2가 리턴될 것이다.

- 이번엔 오른쪽 서브트리를 살펴보면, 루트에서 재귀문이 호출되고(depth == 1), 또다시 루트가 '20'인 서브트리에서 재귀문이 호출되고(depth == 2), 또다시 루트가 각각 '15' '7'인 노드에서 재귀문이 호출된다(depth == 3). 이 두 노드의 자식 노드들은 비어있으므로 depth == 3이 리턴될 것이고, 우리가 찾고자하는 최대 깊이를 찾기 위해선 최상단 루트노드를 기준으로 왼쪽 서브트리, 오른쪽 서브트리의 깊이중 최댓값을 리턴하면 되므로 max를 사용해 최대 깊이를 리턴한다.

 

※ 헷갈렸던점

- if not root는 자바로 표현하면 if(root != null)과 같고, 또 if root != None : 과 같이 표현 할 수 있다.

- 처음에 빈 트리를 생각했을때, 맨 처음 if not root : return depth를 보고 헷갈렸다. ("아니 루트가 아예 없는 텅 빈 트리면 0을 리턴해야 하는데 도대체 depth = 0은 어디에 초기화 되어있지? depth = 0으로 초기화를 시키면 그냥 return depth 일텐데, 초기화도 되지 않은 depth를 어떻게 리턴한다는거지? 함수의 반환형은 int인데,,,

- main함수에서 호출하는건 maxDepth함수이다. maxDepth함수를 살펴보면 dfs다음에 바로 return dfs(root, 0)이다. 즉, maxDepth함수를 호출하면 dfs(root, 0)를 호출한다. 즉, 여기서 depth를 0으로 초기화 시키면 된다.

 

항상 파이썬에서는 indentation을 신경 써야 할것같다