Giả sử chúng ta có một cây nhị phân, chúng ta phải tìm các giá trị của ranh giới của nó theo hướng ngược chiều kim đồng hồ bắt đầu từ gốc. Ở đây ranh giới bao gồm ranh giới bên trái, các lá và ranh giới bên phải theo thứ tự không có các nút trùng lặp.
-
Ranh giới bên trái là đường dẫn từ gốc đến nút ngoài cùng bên trái.
-
Ranh giới bên phải là đường dẫn từ gốc đến nút ngoài cùng bên phải.
-
Khi gốc không có cây con bên trái hoặc cây con bên phải, thì bản thân gốc là ranh giới bên trái hoặc ranh giới bên phải.
Vì vậy, nếu đầu vào giống như
thì đầu ra sẽ là [1,2,4,7,8,9,10,6,3]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định ret mảng
-
Xác định một hàm leftBoundary (), hàm này sẽ sử dụng nút,
-
nếu nút là null hoặc nút là lá, thì -
-
trở lại
-
-
chèn giá trị của nút vào ret
-
nếu bên trái của nút có mặt, thì -
-
leftBoundary (bên trái của nút)
-
-
Nếu không
-
leftBoundary (bên phải của nút)
-
-
Xác định một hàm rightBoundary (), điều này sẽ sử dụng nút,
-
nếu nút là null hoặc nút là lá, thì -
-
trở lại
-
-
chèn giá trị của nút vào ret
-
nếu bên phải của nút hiện diện, thì -
-
rightBoundary (bên trái của nút)
-
-
Nếu không
-
rightBoundary (bên phải của nút)
-
-
Xác định một hàm lá (), điều này sẽ lấy nút,
-
nếu nút không có, thì -
-
trở lại
-
-
nếu nút là lá, thì -
-
chèn val của nút vào ret
-
-
rời khỏi (bên trái của nút)
-
rời khỏi (bên phải của nút)
-
Từ phương thức chính, hãy làm như sau -
-
Xóa mảng ret
-
nếu root không có mặt, thì -
-
trả lại ret
-
-
chèn val của root vào ret
-
leftBoundary (bên trái của thư mục gốc)
-
lá (bên trái của gốc);
-
lá (bên phải gốc);
-
rightBoundary (bên phải của thư mục gốc)
-
trả lại ret
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> 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:
vector<int> ret;
void leftBoundary(TreeNode* node){
if (!node || node->val == 0 || (!node->left && !node->right))
return;
ret.push_back(node->val);
if (node->left && node->left->val != 0)
leftBoundary(node->left);
else
leftBoundary(node->right);
}
void rightBoundary(TreeNode* node){
if (!node || node->val == 0 || (!node->left && !node->right))
return;
if (node->right && node->right->val != 0) {
rightBoundary(node->right);
}
else {
rightBoundary(node->left);
}
ret.push_back(node->val);
}
void leaves(TreeNode* node){
if (!node || node->val == 0)
return;
if (!node->left && !node->right) {
ret.push_back(node->val);
}
leaves(node->left);
leaves(node->right);
}
vector<int> boundaryOfBinaryTree(TreeNode* root){
ret.clear();
if (!root)
return ret;
ret.push_back(root->val);
leftBoundary(root->left);
leaves(root->left);
leaves(root->right);
rightBoundary(root->right);
return ret;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,4,5,6,NULL,NULL,NULL,7,8,9,10};
TreeNode *root = make_tree(v);
print_vector(ob.boundaryOfBinaryTree(root));
} Đầu vào
{1,2,3,4,5,6,NULL,NULL,NULL,7,8,9,10} Đầu ra
[1, 2, 4, 7, 8, 9, 10, 6, 3, ]