이진 트리가 하나 주어지고, 값 v와 깊이 d도 함께 주어진다고 가정해 봅시다. 이때 우리는 주어진 깊이 d 위치에 값이 v인 노드들로 이루어진 새로운 행(row)을 추가해야 합니다. 루트 노드는 깊이 1에 해당합니다.
이 작업을 수행하려면 다음 규칙을 따라야 합니다.
- 깊이 d-1에 있는 모든 유효한 트리 노드 N에 대해, 값이 v인 두 개의 새로운 노드를 생성하여 각각 N의 왼쪽 서브트리 루트와 오른쪽 서브트리 루트로 만듭니다.
- N의 원래 왼쪽 서브트리는 새로 생성된 왼쪽 노드의 왼쪽 자식으로 연결되고, 원래 오른쪽 서브트리는 새로 생성된 오른쪽 노드의 오른쪽 자식으로 연결됩니다.
만약 깊이 d가 1이라면, 즉 d-1 깊이가 존재하지 않는 경우에는 값이 v인 새로운 노드를 생성하여 전체 트리의 새로운 루트로 만들고, 기존 트리 전체는 이 새 루트의 왼쪽 서브트리가 됩니다.
예제 살펴보기
예를 들어 입력이 다음과 같다고 가정해 보겠습니다.
그렇다면 출력 결과는 다음과 같습니다.
해결 접근 방법
이 문제를 해결하기 위해 다음 단계를 따릅니다.
d가 1인 경우:
- v 값을 가진 새 노드 temp를 생성합니다.
- temp의 왼쪽 자식을 현재 루트로 설정합니다.
- 루트를 temp로 교체합니다.
그 외의 경우:
- (노드 포인터, 깊이) 쌍을 저장할 스택 st를 정의합니다.
- {root, 2}를 스택에 삽입합니다. 루트의 자식들은 깊이 2에 있기 때문입니다.
- 스택이 빌 때까지 다음 과정을 반복합니다.
- 스택의 최상위 요소를 꺼내어 깊이(lvl)와 노드(node)를 추출합니다.
- lvl이 d와 같다면:
- v 값을 가진 새 노드 temp1과 temp2를 생성합니다.
- temp1의 왼쪽 자식에 node의 기존 왼쪽 자식을 연결하고, temp2의 오른쪽 자식에 node의 기존 오른쪽 자식을 연결합니다.
- node의 왼쪽 자식을 temp1로, 오른쪽 자식을 temp2로 설정합니다.
- 그렇지 않다면:
- node의 왼쪽 자식이 유효하면 {왼쪽 자식, lvl + 1}을 스택에 삽입합니다.
- node의 오른쪽 자식이 유효하면 {오른쪽 자식, lvl + 1}을 스택에 삽입합니다.
최종적으로 루트를 반환합니다.
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;
}
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 == NULL || curr->val == 0){
cout << "null" << ", ";
}
else{
cout << curr->val << ", ";
}
}
}
cout << "]"<<endl;
}
class Solution {
public:
TreeNode* addOneRow(TreeNode* root, int v, int d) {
if (d == 1) {
TreeNode* temp = new TreeNode(v);
temp->left = root;
root = temp;
}
else {
stack<pair<TreeNode*, int> > st;
st.push({ root, 2 });
int lvl = 0;
pair<TreeNode*, int> temp;
TreeNode* node;
while (!st.empty()) {
temp = st.top();
st.pop();
lvl = temp.second;
node = temp.first;
if (lvl == d) {
TreeNode* temp1 = new TreeNode(v);
TreeNode* temp2 = new TreeNode(v);
temp1->left = node->left;
temp2->right = node->right;
node->left = temp1;
node->right = temp2;
}
else {
if (node->left && node->left->val != 0) {
st.push({ node->left, lvl + 1 });
}
if (node->right && node->right->val != 0) {
st.push({ node->right, lvl + 1 });
}
}
}
}
return root;
}
};
main(){
Solution ob;
vector<int> v = {4,2,6,3,1,5};
TreeNode *root = make_tree(v);
tree_level_trav(ob.addOneRow(root, 1, 2));
}입력
{4,2,6,3,1,5}, 1, 2출력
[4, 1, 1, 2, 6, 3, 1, 5]