⭐️ LeetCode 알고리즘 풀이 (with Python)

# Maximum Depth of Binary Tree

[Quetion]

LeetCode 104. Maximum Depth of Binary Tree

📌 접근법

[문제 이해]

• 이진 트리의 깊이를 구하는 문제

깊이를 구하기 위해서는 깊이 우선 탐색(DFS) 방법으로 접근이 필요하다.
DFS는 전위, 중위, 후위 방식이 있는데 이번에는 전위순회 방식을 활용했다.

• 현재 노드를 방문 처리하고 깊이를 저장
• 왼쪽 서브 트리를 방문 후 오른쪽 서브 트리를 방문하는 재귀호출
• 재귀 호출 전 깊이를 증가

💻 구현

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        depth=0
        result=[]
        self.preorder(root, depth, result)
        
        # depth가 담긴 리스트의 중복 제거와 정렬
        result=sorted(set(result))
        return result[-1]
    
    # 전위순회
    def preorder(self, root, depth, result):
        if root is None:
            result.append(depth)
            pass
        else:
            depth+=1
            self.preorder(root.left, depth, result)
            self.preorder(root.right, depth, result)

Runtime: 37ms | Memory: 18.6MB
LeetCode 코드 중 Runtime 96%, Memory 74% 해당하는 결과

📌 로직 핵심

• 왼쪽과 오른쪽 서브트리를 순회하며 result 리스트에 깊이를 저장
• 저장된 깊이 중 중복을 제거하고 오름차순 정렬
• 값이 가장 큰 result의 마지막 값 반환

---

📝 Maximum Depth of Binary Tree 회고

• 시간복잡도는 N=트리 노드의 수 라고 할 때 전위순회 과정에서 O(N), 중복제거와 정렬과정에서 O(NlogN)이므로 O(N + NlogN) = O(NlogN)을 가진다.
• 공간복잡도는 최악의 경우 트리의 모든 리프노드의 깊이를 저장할 수 있으므로 O(N)이 된다.
• 다른 솔루션들을 참고해보니 단순 재귀의 방법으로 깊이를 구하고 max()함수로 최대 깊이를 구한 코드가 인상 깊었다.
• 솔루션을 참고하여 코드를 다시 변경해보았다.

# 수정된 코드
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right))+1

Runtime: 37ms ---> 43ms
Memory: 18.6MB ---> 18.5MB

성능상으로는 기존 코드와 크게 차이는 없는 코드이다. 하지만 코드가 훨씬 간결해졌고 Memory를 조금 더 개선할 수 있었다.

이번 문제를 해결하면서 느낀점은 아직 재귀가 익숙하지 않아서 그런지 탐색을 구현하는데 있어서 어려움이 있는 것 같다. 문제를 풀며 익숙해질 수 있도록 더 노력해야겠다 :D