[DSA][Trees] 04. Balanced Binary Tree

LeetCode 110

 

04. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

 

 

[질문하기]

- 빈 트리(루트가 None)인 경우 결과는 true로 처리하나요?

 

[아이디어]

- DFS를 사용하여 재귀적으로 깊이와 balance 여부를 판단하자. 

 

 

[풀이 1] Depth First Search

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def dfs(node):
            if not node:
                return [True, 0]
            
            left, right = dfs(node.left), dfs(node.right)
            isBalanced = left[0] and right[0] and abs(left[1] - right[1]) <= 1
            return [isBalanced, 1 + max(left[1], right[1])]
        
        return dfs(root)[0]

height-balanced 여부를 판단하기 위해서는, 각 노드에서 왼쪽과 오른쪽 서브트리의 깊이 차이를 구해야 하므로, DFS 함수를 만들어 재귀적으로 왼쪽과 오른쪽의 길이를 구하고, 그 차이가 1보다 크면 False를 반환해야 한다.

그런데 이를 위해서는 DFS 함수가 해당 노드의 깊이(height)뿐만 아니라 height-balanced 여부도 함께 반환해야 한다. 따라서 return [balance 여부, 깊이] 형태로 두 값을 함께 반환한다.

각 노드에서는 왼쪽과 오른쪽에서 반환된 깊이와 balance 여부를 이용해, 양쪽이 모두 balanced 하고 두 깊이 차가 1 이하인지를 확인하여 현재 노드가 balanced인지 판단할 수 있다. 위 코드에서 더 나아가서 왼쪽이나 오른쪽 서브트리 중 하나라도 이미 unbalanced인 경우 바로 False를 반환하면 더 이상 불필요한 탐색을 줄여 보다 효율적으로 동작하게 만들 수도 있다.

 

⏱️ 시간복잡도

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

🧠 공간복잡도

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