Giả sử chúng ta có một cây nhị phân, chúng ta cũng có giá trị v và độ sâu d, chúng ta phải thêm một hàng nút có giá trị v ở độ sâu d đã cho. Nút gốc ở độ sâu 1. Chúng ta phải tuân theo quy tắc này để thực hiện thao tác này -
Như chúng ta đã biết độ sâu d, đối với mỗi nút cây hợp lệ N ở độ sâu d-1, chúng ta phải tạo hai nút cây với giá trị v là gốc cây con bên trái của N và gốc cây con bên phải. Và cây con bên trái ban đầu của N sẽ là cây con bên trái của gốc cây con bên trái mới, cây con bên phải ban đầu của nó sẽ là cây con bên phải của gốc cây con bên phải mới. Khi độ sâu d là 1 nghĩa là không có độ sâu d-1 nào cả, thì hãy tạo một nút cây với giá trị v là gốc mới của toàn bộ cây gốc và cây gốc là cây con bên trái của gốc mới.
Vì vậy, nếu đầu vào giống như
thì đầu ra sẽ là
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
nếu d giống với 1 thì -
-
temp =nút mới với giá trị v
-
left of temp:=root
-
root:=temp
-
-
Nếu không
-
Xác định một ngăn xếp các cặp được gọi là st
-
chèn {root, 2} vào st
-
lvl:=0
-
Xác định nhiệt độ một cặp
-
while (not st là trống), do -
-
temp:=phần tử hàng đầu của st
-
xóa phần tử khỏi st
-
lvl:=phần tử thứ hai của temp
-
node:=phần tử đầu tiên của temp
-
nếu lvl giống với d, thì -
-
temp1 =nút mới với giá trị v
-
temp2 =nút mới với giá trị v
-
left of temp1:=left of node
-
right of temp2:=right of node
-
bên trái của nút:=temp1
-
bên phải của nút:=temp2
-
-
Nếu không
-
nếu bên trái của nút là hợp lệ, thì -
-
chèn {bên trái của nút, lvl + 1} vào st
-
-
nếu quyền của nút hợp lệ, thì -
-
chèn {right of node, lvl + 1} vào st
-
-
-
-
-
trả về thư mục gốc
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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));
} Đầu vào
{4,2,6,3,1,5}, 1, 2 Đầu ra
[4, 1, 1, 2, 6, 3, 1, 5, ]