이진 트리의 루트 노드가 주어졌을 때, 모든 노드의 기울기(tilt) 합계를 구해서 반환하는 것이 이번 문제의 목표입니다.
여기서 기울기(tilt)란 각 노드를 기준으로 왼쪽 서브트리에 속한 노드 값들의 합과 오른쪽 서브트리 노드 값들의 합 사이의 절댓값 차이를 의미합니다. 자식 노드가 없는 리프 노드의 경우 기울기를 0으로 계산합니다.
예제
입력
출력: 15
설명: 주어진 이진 트리의 각 노드별 기울기를 계산하면 다음과 같습니다.
- 노드 3의 기울기 = 0
- 노드 5의 기울기 = 0
- 노드 7의 기울기 = 0
- 노드 2의 기울기 = abs(3 − 5) = 2
- 노드 9의 기울기 = abs(0 − 7) = 7
- 노드 4의 기울기 = abs((3 + 5 + 2) − (9 + 7)) = 6
따라서 모든 노드의 기울기 합계는 2 + 7 + 6 = 15입니다.
문제 해결 접근 방식
이 문제는 후위 순회(Post-order Traversal)를 활용하는 것이 가장 효율적입니다. 후위 순회는 '왼쪽 자식 → 오른쪽 자식 → 부모 노드' 순서로 노드를 방문하기 때문에, 자식 노드들의 정보를 먼저 확보한 뒤 부모 노드의 기울기를 계산할 수 있습니다.
트리를 순회하면서 먼저 왼쪽 서브트리와 오른쪽 서브트리의 노드 값 합계를 각각 구하고, 두 값의 절댓값 차이를 해당 노드의 기울기로 계산하여 누적합니다.
알고리즘 단계
- 입력으로 이진 트리를 받습니다.
sumNodes(treenode* node)함수: 루트 노드를 받아 왼쪽·오른쪽 서브트리의 합계를 재귀적으로 계산하고, 각 노드의 기울기를 참조 변수에 누적한 뒤 서브트리 전체의 합을 반환합니다.findTilt(treenode* root)함수: 루트 노드를 입력받아 모든 노드의 기울기 합계를 반환합니다.
C++ 구현 코드
#include<iostream>
using namespace std;
struct treenode {
int data;
treenode * left;
treenode * right;
};
struct treenode * createNode(int d) {
struct treenode * root = new treenode;
root->data = d;
root->left = NULL;
root->right = NULL;
return root;
}
int sumNodes(treenode * root, int & sum) {
if (root == NULL) return 0;
int lsum = sumNodes(root->left, sum);
int rsum = sumNodes(root->right, sum);
sum += abs(lsum - rsum);
return lsum + rsum + root->data;
}
int findTilt(treenode * root) {
int sum = 0;
if (root == NULL) {
return 0;
}
sumNodes(root, sum);
return sum;
}
int main() {
struct treenode * root = NULL;
root = createNode(4);
root->left = createNode(2);
root->right = createNode(9);
root->left->right = createNode(5);
root->left->left = createNode(3);
root->right->right = createNode(7);
cout << findTilt(root) << endl;
return 0;
}
위 코드를 실행하면 아래와 같은 결과가 출력됩니다.
출력
15
주어진 이진 트리에서 모든 노드의 기울기 합계는 15입니다.
복잡도 분석
- 시간 복잡도: O(n) — 트리의 모든 노드를 한 번씩 방문합니다.
- 공간 복잡도: O(h) — 재귀 호출 스택은 트리의 높이(h)에 비례하여 사용됩니다.