[LEETCODE] 104: Maximum Depth of Binary Tree(Python)

Maximum Depth of Binary Tree - LeetCode

문제 설명

주어진 이진 트리의 깊이를 구해보자.

나의 풀이

# 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 func(root,d,depth):
            if root==None:
                return 0
            depth=max(func(root.left,d+1,depth),func(root.right,d+1,depth),d)
            return depth
        
        depth=func(root,1,1)
        return depth

함수를 재귀 호출하면서 트리 깊이를 최대값으로 업데이트한다.

시간복잡도

모든 노드를 탐색하므로 시간복잡도는 O(n)이다.