이진 트리가 있고 값 v와 깊이 d가 있다고 가정하면 주어진 깊이 d에서 값 v를 갖는 노드 행을 추가해야 합니다. 루트 노드는 깊이 1에 있습니다. 이 작업을 수행하려면 이 규칙을 따라야 합니다 -
깊이 d를 알고 있는 것처럼 깊이 d-1의 각 유효한 트리 노드 N에 대해 값 v를 N의 왼쪽 하위 트리 루트와 오른쪽 하위 트리 루트로 사용하여 두 개의 트리 노드를 만들어야 합니다. 그리고 N의 원래 왼쪽 하위 트리는 새 왼쪽 하위 트리 루트의 왼쪽 하위 트리가 되고 원래 오른쪽 하위 트리는 새 오른쪽 하위 트리 루트의 오른쪽 하위 트리가 됩니다. 깊이 d가 1이면 깊이 d-1이 전혀 없음을 의미합니다. 그러면 전체 원래 트리의 새 루트로 값 v를 사용하여 트리 노드를 만들고 원래 트리는 새 루트의 왼쪽 하위 트리입니다.
따라서 입력이 다음과 같으면
그러면 출력은
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
d가 1과 같으면 -
-
temp =값이 v
인 새 노드 -
임시의 왼쪽 :=루트
-
루트 :=임시
-
-
그렇지 않으면
-
st
라는 쌍의 스택 하나를 정의합니다. -
{ root, 2 }를 st
에 삽입 -
레벨 :=0
-
한 쌍의 온도 정의
-
동안(st가 비어 있지 않음) -
-
temp :=st의 최상위 요소
-
st
에서 요소 삭제 -
lvl :=temp의 두 번째 요소
-
node :=temp의 첫 번째 요소
-
lvl이 d와 같으면 -
-
temp1 =값이 v
인 새 노드 -
temp2 =값이 v
인 새 노드 -
temp1의 왼쪽 :=노드의 왼쪽
-
temp2의 오른쪽 :=노드의 오른쪽
-
노드 왼쪽 :=temp1
-
노드 오른쪽 :=temp2
-
-
그렇지 않으면
-
노드의 왼쪽이 유효하면 -
-
{노드의 왼쪽, lvl + 1}을 st에 삽입
-
-
노드의 오른쪽이 유효한 경우 -
-
st에 {노드 오른쪽, lvl + 1} 삽입
-
-
-
-
-
루트 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#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, ]