리트코드 - 104. Maximum Depth of Binary Tree

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

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

 

모든 노드를 dfs 탐색을 진행하면서 탐색하므로, 시간 복잡도는 O(n)이다.

 

공간 복잡도는 트리가 완전히 편향된 경우 트리의 높이만큼 깊이를 가지게 되므로, 최대 깊이가 h라고 하면 O(h)의 공간 복잡도를 가진다.

균형잡인 트리의 경우 O(log())의 시간 복잡도를 가진다.