문제 개요
이진 트리의 루트(root)가 주어졌을 때, 서로 다른 두 노드 A와 B에 대해 V = |A의 값 − B의 값|을 만족하고 A가 B의 조상(ancestor)인 경우의 최댓값 V를 구하는 것이 목표입니다.
예를 들어 아래와 같은 트리가 있다고 가정해 보겠습니다.
이 트리에서 조상 노드와 자손 노드 간의 차이는 [(8 − 3), (7 − 3), (8 − 1), (10 − 13)]이 되며, 그중 (8 − 1) = 7이 가장 큰 값입니다. 따라서 출력 결과는 7입니다.
접근 방법
이 문제는 DFS(깊이 우선 탐색)를 활용한 재귀적 접근으로 해결할 수 있습니다. 핵심 아이디어는 트리를 순회하면서 루트부터 현재 노드까지 경로상의 최솟값(currMin)과 최댓값(currMax)을 함께 전달하는 것입니다. 각 노드에 도달할 때마다 현재 노드의 값과 경로상 최솟값·최댓값 사이의 절댓값 차이를 계산하여 답을 갱신합니다.
구체적인 단계는 다음과 같습니다.
- 결괏값을 저장할 변수 ans를 0으로 초기화합니다.
- 트리 노드, currMin, currMax를 매개변수로 받는 solve() 메서드를 정의합니다.
- 노드가 null이면 즉시 반환합니다.
- ans를 max(ans, |노드의 값 − currMin|, |노드의 값 − currMax|)로 갱신합니다.
- 왼쪽 자식에 대해 solve(left, min(노드의 값, currMin), max(노드의 값, currMax))를 호출합니다.
- 오른쪽 자식에 대해 solve(right, min(노드의 값, currMin), max(노드의 값, currMax))를 호출합니다.
- 메인 함수에서 solve(root, root의 값, root의 값)을 호출한 후 ans를 반환합니다.
이 방법은 모든 노드를 한 번씩만 방문하므로 시간 복잡도는 O(n)이며, 재귀 호출 스택으로 인한 공간 복잡도는 트리의 높이 h에 비례하여 O(h)입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
}else{
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
}else{
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
}
return root;
}
class Solution {
public:
int ans;
void solve(TreeNode* node, int currMin, int currMax){
if (!node || node->val == 0) return;
ans = max({ans, abs(node->val - currMin), abs(node->val - currMax)});
solve(node->left, min(node->val, currMin), max(node->val, currMax));
solve(node->right, min(node->val, currMin), max(node->val, currMax));
}
int maxAncestorDiff(TreeNode* root) {
ans = 0;
solve(root, root->val, root->val);
return ans;
}
};
main(){
vector<int> v = {8,3,10,1,6,NULL,14,NULL,NULL,4,7,13};
TreeNode *root = make_tree(v);
Solution ob;
cout << (ob.maxAncestorDiff(root));
}입력
[8,3,10,1,6,null,14,null,null,4,7,13]
출력
7
마무리
이 문제는 코딩 테스트에서 자주 등장하는 'Maximum Difference Between Node and Ancestor' 유형과 동일합니다. DFS 순회 중 경로의 최솟값과 최댓값을 함께 추적하는 패턴은 트리 관련 다양한 문제에 널리 응용되므로, 위 구현 예제를 직접 실행해 보며 동작 원리를 익혀두는 것을 권장합니다.