[Top Interview Questions] 104. Maximum Depth of Binary Tree

정답)

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        # Recursive 함수
        def helper(root):
        
            # Base Case
            if not root:
                return 0
            
            # Recursive Calls 
            # root의 왼쪽 subtree의 depth를 구해줌
            count1 = helper(root.left)
            
            # root의 오른쪽 subtree의 depth를 구해줌
            count2 = helper(root.right)

            # 왼쪽/오른쪽 sub tree 중 더 깊은 트리와 루트 노드 1개를 합쳐 리턴
            return max(count1, count2) + 1
        
        return helper(root)

문제)

문제출처

 

Binary Tree의 루트가 주어졌을 때, 그 트리의 최대 깊이를 구하시오.

최대 깊이는 트리의 줄기 중 가장 멀리 뻗쳐있는 줄기의 리프 개수를 의미합니다.

 

예시 1)

 

root = [3, 4, 20, Null, Null, 15, 7]

root = [3, 4, 20, Null, Null, 15, 7]

output = 3

 

예시 2)

root = [1, Null, 2]

output = 2

 

제한)

노드의 숫자는 0~10000개 입니다.

-100 <= Node.val <= 100

풀이)

기본원리)

Recursive 함수를 이용하여 루트의 왼쪽/오른쪽 subtree의 최대 길이를 구합니다.

 

그 두 숫자를 비교하여 더 큰 숫자에 마지막 루트 노드까지 포함해 1을 더한 정수 값을 리턴합니다.

Base Case)

먼저 recursive 함수의 base case를 찾아줍시다.

 

제한에서 노드의 개수가 0이 될 수도 있다고 했기 때문에 root가 존재하지 않을 수도 있습니다.

섣불리 root의 child node들을 base case로 해버렸다간 코드가 실행조차 되지 않을 수도 있습니다.

 

그러므로 베이스 케이스는 root가 존재하는지 확인해 주겠습니다.

만약 존재하지 않는다면 그 트리의 최대 깊이는 0이 되는 것이기 때문에 0을 리턴합니다.

 

def maxDepth(self, root: Optional[TreeNode]) -> int:
        def helper(root):
            if not root:
                return 0

Recursive Calls 1)

제가 recursive 함수를 만들 때 단순하게 생각해야 된다고 얘기했죠?

이번에도 단순하게 생각해 봅시다.

 

저희가 디자인하는 recursive 함수는 주어진 트리의 최대 깊이를 리턴하도록 설정할 것입니다.

 

그렇다면 root의 왼쪽/오른쪽 트리들의 최대 깊이를 리턴하게 한 후 그 값들을 비교해서 더 큰 숫자와

마지막 루트노드 1개를 더해 최종값을 리턴하게 하면 어떨까요?

 

helper() 설계도

일단은 설계 단계니까 각 subtree에서 얻은 숫자들을 변수에 저장해 주죠.

 

def maxDepth(self, root: Optional[TreeNode]) -> int:
        def helper(root):
            if not root:
                return 0
            
            count1 = helper(root.left)
            count2 = helper(root.right)

Recursive Calls 2)

각 subtree에서 최대 깊이를 받았다면 그 두 변수를 비교해 더 큰 숫자를 찾고 그 큰 숫자에 1을 더해주면 되겠습니다.

 

최대 정수값을 지닌 변수를 찾는 효율적인 함수 중에 max() 함수가 있습니다.

이 함수를 이용해 더 큰 값을 구하고 1을 더해줍니다.

 

그리고 그렇게 구한 전체 트리의 최대 깊이를 리턴해주면 끝납니다.

 

def maxDepth(self, root: Optional[TreeNode]) -> int:
        def helper(root):
            if not root:
                return 0
            
            count1 = helper(root.left)
            count2 = helper(root.right)

            return max(count1, count2) + 1
        
        return helper(root)

디버깅)

root = [3, 4, 20, Null, Null, 15, Null]

 

root = [3, 4, 20, Null, Null, 15, Null]

(1)

helper(3) -> helper(4) -> helper(Null)

return 0

 

(2)

helper(Null)

return 0

 

(3)

helper(4)

return 1    # max(0, 0) + 1

 

위 1~3까지의 스텝

 

(1)

helper(20) -> helper(15) -> helper(Null)

return 0

 

(2)

helper(Null)

return 0

 

(3)

helper(15)

return 1    # max(0, 0) + 1

 

(4)

helper(Null)

return 0

 

(5)

helper(20)

return 2    # max(1, 0) + 1

 

위 1~5까지의 스텝

helper(3)

return 3    # max(1, 2) + 1

 

 

Recursion은 아무래도 연습량 싸움인가 봅니다. 물론 생각할 줄 아는 능력도 중요하지만 그걸 실제로 쓸 줄 아는 게 중요하잖아요? 고작 몇 문제 밖에 안 풀었지만 확실히 설계하는 관점이 잡히는 게 느껴집니다. (그래도 어렵 ㅎㅎ...)

 

오늘도 풀이과정에 질문이나 잘못된 부분 있다면 알려주시면 감사하겠습니다 :)