이진 트리의 높이 균형이란?
하나의 이진 트리(binary tree)가 주어졌을 때, 그 트리의 높이가 균형 잡혀 있는지 확인해야 합니다. 높이 균형(height-balanced) 트리란 트리에 속한 모든 노드에 대해 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이의 절댓값이 0 또는 1인 트리를 말합니다. 이 조건은 AVL 트리와 같은 자가 균형(self-balancing) 이진 탐색 트리의 핵심 개념이기도 합니다.
예를 들어 아래와 같은 트리가 입력으로 주어지면,
출력 결과는 True(균형 잡힌 트리)가 됩니다.
문제 해결 접근 방법
이 문제는 깊이 우선 탐색(DFS)을 재귀적으로 수행하면 효율적으로 해결할 수 있습니다. 각 노드에서 왼쪽과 오른쪽 서브트리의 높이를 동시에 계산하고, 그 차이가 1을 넘는 순간 균형이 깨진 것으로 판단하는 방식입니다. 단계별 과정은 다음과 같습니다.
- dfs() 함수를 정의하고 노드(node)를 인자로 전달합니다.
- 노드가 null이면 0을 반환합니다.
- l := 1 + dfs(노드의 왼쪽 자식)
- r := 1 + dfs(노드의 오른쪽 자식)
- |l − r| > 1이면 ret := false로 설정합니다.
- l과 r 중 더 큰 값을 반환합니다.
- 메인 메서드에서는 다음을 수행합니다.
- ret := true로 초기화합니다.
- dfs(root)를 호출합니다.
- ret을 반환합니다.
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
bool ret;
int dfs(TreeNode* node){
if(!node)
return 0;
int l = 1 + dfs(node->left);
int r = 1 + dfs(node->right);
if(abs(l - r) > 1)
ret = false;
return max(l, r);
}
bool isBalanced(TreeNode* root) {
ret = true;
dfs(root);
return ret;
}
};
main(){
Solution ob;
TreeNode *root = new TreeNode(25);
root->left = new TreeNode(19);
root->right = new TreeNode(4);
root->left->left = new TreeNode(9);
root->left->right = new TreeNode(7);
cout << (ob.isBalanced(root));
}입력
TreeNode *root = new TreeNode(25); root->left = new TreeNode(19); root->right = new TreeNode(4); root->left->left = new TreeNode(9); root->left->right = new TreeNode(7);
출력
1
코드 설명 및 복잡도 분석
dfs() 함수는 각 노드를 재귀적으로 방문하며 해당 노드를 루트로 하는 서브트리의 높이를 계산합니다. 리프 노드의 높이는 1이며, 부모 노드로 올라갈수록 1씩 증가합니다. 왼쪽 높이 l과 오른쪽 높이 r의 차이가 1보다 크면 멤버 변수 ret을 false로 변경하여 트리의 균형이 깨졌음을 기록합니다.
isBalanced() 함수는 ret을 true로 초기화한 뒤 dfs()를 호출하고 최종 결과를 반환합니다. 출력이 1로 표시되는 이유는 bool 값 true가 정수 1로 출력되었기 때문입니다.
- 시간 복잡도: O(n) — 모든 노드를 한 번씩 방문합니다.
- 공간 복잡도: O(h) — 재귀 호출 스택의 깊이는 트리의 높이 h에 비례합니다.