[LeetCode] 104번 Maximum Depth of Binary Tree 문제 풀이 (파이썬)

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

Maximum Depth of Binary Tree - LeetCode

재귀적으로 풀 수 있었다. 다이나믹 프로그래밍의 원리를 이용해서, 특정 노드에서의 최대 깊이는 자식 노드의 최대 깊이에 1을 더한 것이라는 점에 착안하여 풀었다. 다만 재귀적으로 푸는 과정에서 바로 max값을 구해주었기 때문에 메모이제이션은 사용하지 않았다.

BFS로 푼 풀이들도 있는 것 같은데 다시 풀어봐도 괜찮을 듯.

# 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_depth(node):
            while node: # 노드가 null이 아닌 경우
                if not node.left and not node.right: # 단말 노드인 경우
                    return 1
                
                # 자식 노드들의 최고 깊이에 1을 더한 값을 리턴함
                return max(get_depth(node.left), get_depth(node.right)) + 1
            
            return 0 # 노드가 null인 경우에는 0 반환
        
        return get_depth(root) # return 빼먹을 경우 다 풀어놓고 오답 판정 받을 수 있으니 꼼꼼히 하자