이진 트리와 정수 target이 주어졌을 때, 값이 target과 같은 모든 리프 노드를 삭제해야 합니다. 중요한 점은 target 값을 가진 리프 노드를 삭제한 후, 그 부모 노드가 새로운 리프 노드가 되었고 역시 target 값을 가지고 있다면 해당 노드도 삭제해야 한다는 것입니다. 더 이상 삭제할 수 없을 때까지 이 과정을 반복합니다.
예를 들어 아래와 같은 트리가 있고 target이 2라고 가정하면, 최종적으로 얻게 되는 트리는 마지막 트리와 같습니다.
문제 해결 접근 방법
이 문제는 재귀(후위 순회) 방식으로 해결할 수 있습니다. 자식 노드부터 먼저 처리한 뒤 부모 노드가 리프 노드가 되었는지 판단하는 것이 핵심입니다.
루트와 target을 인자로 받는 재귀 함수 remLeaf()를 정의합니다.
루트가 null이면 null을 반환합니다.
left := remLeaf(루트의 왼쪽 자식, target)으로 왼쪽 서브트리를 처리합니다.
right := remLeaf(루트의 오른쪽 자식, target)으로 오른쪽 서브트리를 처리합니다.
left와 right가 모두 null이고, 루트의 값이 target과 같다면 현재 노드도 리프 노드가 되었으므로 null을 반환하여 삭제합니다.
루트의 left에 left를, right에 right를 연결합니다.
루트를 반환합니다.
예제 코드 (C++)
아래 구현 예제를 통해 동작 방식을 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = 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;
}
void tree_level_trav(TreeNode*root){
if (root == NULL) return;
cout << "[";
queue<TreeNode *> q;
TreeNode *curr;
q.push(root);
q.push(NULL);
while (q.size() > 1) {
curr = q.front();
q.pop();
if (curr == NULL){
q.push(NULL);
} else {
if(curr->left)
q.push(curr->left);
if(curr->right)
q.push(curr->right);
if(curr->val == 0 || curr == NULL){
cout << "null" << ", ";
} else {
cout << curr->val << ", ";
}
}
}
cout << "]"<<endl;
}
class Solution {
public:
TreeNode* removeLeafNodes(TreeNode* root, int target) {
if(!root || root->val == 0) return NULL;
TreeNode* left = removeLeafNodes(root->left, target);
TreeNode* right = removeLeafNodes(root->right, target);
if(!left && !right && root->val == target){
return NULL;
}
root->left = left;
root->right = right;
return root;
}
};
main() {
vector<int> v1 = {1,2,3,2,NULL,2,4};
TreeNode *root = make_tree(v1);
Solution ob;
tree_level_trav(ob.removeLeafNodes(root, 2));
}입력
[1,2,3,2,null,2,4] 2
출력
[1, 3, 4]
동작 원리 설명
위 코드에서 핵심은 removeLeafNodes() 함수입니다. 이 함수는 후위 순회(postorder traversal) 방식으로 동작합니다. 즉, 왼쪽 자식과 오른쪽 자식을 먼저 재귀적으로 처리한 후에 현재 노드를 검사합니다. 자식들이 모두 처리된 시점에는 현재 노드가 리프 노드인지 정확하게 판단할 수 있습니다. 만약 양쪽 자식이 모두 null이고 노드의 값이 target과 일치한다면, 해당 노드는 삭제 대상이므로 null을 반환합니다. 이렇게 하면 삭제로 인해 새롭게 리프 노드가 된 부모 노드까지 연쇄적으로 처리할 수 있습니다.
시간 복잡도는 트리의 모든 노드를 한 번씩 방문하므로 O(n)이며, 공간 복잡도는 재귀 호출 스택 깊이에 의해 최악의 경우(편향된 트리) O(n), 균형 잡힌 트리의 경우 O(log n)입니다.