Giả sử chúng ta có một cây nhị phân, một nút đích và một giá trị K. Chúng ta phải tìm một danh sách các giá trị của tất cả các nút có khoảng cách K từ nút đích.
Vì vậy, nếu đầu vào là root =[3,5,1,6,2,0,8, null, null, 7,4], target =5, K =2, thì đầu ra sẽ là [7,4 , 1], điều này là do các nút cách nút đích 2 khoảng cách có các giá trị 7, 4 và 1.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Định nghĩa một hàm dfs (), hàm này sẽ lấy nút, pa khởi tạo nó bằng NULL,
-
nếu nút là null, thì -
-
trở lại
-
-
cha [node]:=pa
-
dfs (bên trái của nút, nút)
-
dfs (bên phải của nút, nút)
-
Từ phương thức chính, thực hiện như sau -
-
Xác định ans mảng
-
dfs (gốc)
-
Xác định một hàng đợi q cho cặp (nút, giá trị)
-
chèn {target, 0} vào q
-
Xác định một tập hợp được gọi là đã truy cập
-
chèn mục tiêu vào đã truy cập
-
while (không phải q trống), do -
-
Xác định một cặp p:=phần tử đầu tiên của q
-
xóa phần tử khỏi q
-
level:=phần tử thứ hai của nhiệt độ
-
node =phần tử đầu tiên của tạm thời.
-
nếu cấp bằng k, thì -
-
chèn giá trị của nút vào cuối ans
-
-
nếu bên trái của nút không rỗng và mức + 1 <=k và bên trái của nút không được truy cập, thì
-
chèn {bên trái của nút, mức + 1}) vào q
-
chèn bên trái của nút vào nhóm đã truy cập
-
-
nếu bên phải của nút không rỗng và mức + 1 <=k và bên phải của nút không được truy cập, thì
-
chèn {bên phải của nút, mức + 1}) vào q
-
chèn bên phải của nút vào tập hợp đã truy cập
-
-
nếu [nút] cha không phải là NULL và cấp + 1 <=k và [nút] cha không được truy cập, thì -
-
chèn {cha [nút], cấp + 1} vào q
-
chèn [nút] cha vào đã truy cập
-
-
-
trả lại ans
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;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
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:
map <TreeNode*, TreeNode*> parent;
void dfs(TreeNode* node, TreeNode* pa = NULL){
if (!node)
return;
parent[node] = pa;
dfs(node->left, node);
dfs(node->right, node);
}
vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
vector<int> ans;
parent.clear();
dfs(root);
queue<pair<TreeNode*, int> > q;
q.push({ target, 0 });
set<TreeNode*> visited;
visited.insert(target);
while (!q.empty()) {
pair<TreeNode*, int> temp = q.front();
q.pop();
int level = temp.second;
TreeNode* node = temp.first;
if (level == k) {
ans.push_back(node->val);
}
if ((node->left && node->left->val != 0) && level + 1 <= k && !visited.count(node->left)) {
q.push({ node->left, level + 1 });
visited.insert(node->left);
}
if ((node->right && node->right->val != 0) && level + 1 <= k && !visited.count(node->right)){
q.push({ node->right, level + 1 });
visited.insert(node->right);
}
if (parent[node] != NULL && level + 1 <= k && !visited.count(parent[node])) {
q.push({ parent[node], level + 1 });
visited.insert(parent[node]);
}
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {3,5,1,6,2,0,8,NULL,NULL,7,4};
TreeNode *root = make_tree(v);
TreeNode *target = root->left;
print_vector(ob.distanceK(root, target, 2));
} Đầu vào
{3,5,1,6,2,0,8,NULL,NULL,7,4} Đầu ra
[7, 4, 1, ]