[LeetCode]Maximum Depth of Binary Tree

https://leetcode.com/problems/maximum-depth-of-binary-tree/

Maximum Depth of Binary Tree - LeetCode

 

문제 분석

트리에서 가장 긴 depth 값을 구하는 문제, 즉 트리의 레벨을 구하는 문제입니다.

 

처음 시도한 답안 

# 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 get_tree_level(root):
            if root is None:
                return 0
            # return max(get_tree_level(root.left), get_tree_level(root.right)) + 1 도 가능
            return max(get_tree_level(root.left) + 1, get_tree_level(root.right) + 1)
        
        return get_tree_level(root)

접근 방법

1. 루트 노드가 존재하지 않다면 트리의 레벨은 0 입니다.
2. 트리의 왼쪽 노드들의 레벨과 트리의 오른쪽 노드들의 레벨을 구해 큰 값을 레벨로 설정합니다.
3. 이 때, 함수가 1번 호출될때마다 값을 1 증가시켜 레벨을 구합니다.

root = [3, 9, 2, null, null, 15, 7]의 Input 값을 가지고 어떻게 값이 바뀌는지 확인해보겠습니다.

(함수 호출시의 값은 루트 노드의 val로 칭하겠습니다.)

1. get_tree_level(3)
2. max(get_tree_level(9) + 1, get_tree_level(20) + 1)
3. max(
       max(get_tree_level(None) + 1, get_tree_level(None) + 1) + 1,
       max(get_tree_level(15) + 1, get_tree_level(7) + 1 )) +1,
   )
4. max(
       max(get_tree_level(None) + 1, get_tree_level(None) + 1) + 1,
       max(
           max(get_tree_level(None) + 1, get_tree_level(None) + 1) + 1,
           max(get_tree_level(None) + 1, get_tree_level(None) + 1) + 1,
       ) + 1,
   )
5. max(
       max(get_tree_level(None) + 1, get_tree_level(None) + 1) + 1,
       max(
           max(0 + 1, 0 + 1) + 1,
           max(0 + 1, 0 + 1) + 1,
       ) + 1,
   )
6. max(
       max(0 + 1, 0 + 1) + 1,
       max(2, 2) + 1,
   )
7. max(2, 3)
8. return 3