[DSA][Trees] 03. Diameter of Binary Tree

LeetCode 543

 

03. Diameter of Binary Tree

Given the root of a binary tree, return the length of the diameter of the tree.
The diameter of a binary tree is the length of the longest path between any two nodes in a tree.
This path may or may not pass through the root.
The length of a path between two nodes is represented by the number of edges between them.

 

 

[질문하기]

- 빈 트리(루트가 None)인 경우 diameter는 0으로 처리하나요?

 

[아이디어]

- DFS를 사용하여 최대 깊이를 구하고, 각 호출에서 현재까지의 최대 diameter를 갱신하자.

 

 

[풀이 1] Depth First Search

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        res = 0

        def dfs(root):
            nonlocal res

            if not root:
                return 0
            
            left = dfs(root.left)
            right = dfs(root.right)
            res = max(res, left + right)

            return 1 + max(left, right)
        
        dfs(root)
        return res

하나의 노드 기준으로 diameter(지름)를 구하면, 왼쪽 서브트리의 최대 깊이 + 오른쪽 서브트리의 최대 깊이가 된다.

따라서 재귀 함수가 반환해야 하는 값은 지름(diameter) 그 자체가 아니라, 왼쪽과 오른쪽 중 더 깊은 쪽의 깊이다.
즉, dfs 함수는 현재 노드를 기준으로 한 지름을 계산하여 전체 지름의 최댓값을 갱신하고, 현재 노드 기준으로 왼쪽 또는 오른쪽 중 더 깊은 깊이 + 1을 반환해서 부모 노드가 자신의 최대 깊이를 알 수 있도록 하는 2가지 역할을 해야 한다.

 

이를 위해 dfs(root.left)로 왼쪽 서브트리의 최대 깊이를 구하고, dfs(root.right)로 오른쪽 서브트리의 최대 깊이를 구한 후, left + right로 해당 노드를 기준으로 한 지름을 계산하여 전역 변수의 최댓값을 갱신하고 1 + max(left, right)를 반환하여 현재 노드까지 포함한 최대 깊이를 전달한다.

 

⏱️ 시간복잡도

이 알고리즘은 트리의 모든 노드를 한 번씩 방문하므로, 시간 복잡도는 O(n)이다.

🧠 공간복잡도

공간 복잡도는 재귀 호출 스택의 깊이에 의해 결정되기 때문에 O(h)에 비례하고 따라서 공간 복잡도는 최악의 경우 O(N) (Skew 트리)이고, 평균적으로는 O(log N) (균형 잡힌 트리)이다.