Giả sử chúng ta có một cây nhị phân, nếu chúng ta nhìn cây từ phía bên trái, thì chúng ta có thể thấy một số phần tử của nó. chúng ta phải hiển thị các yếu tố đó. Vì vậy, nếu cây như -
Đầu ra sẽ là [1,2,5]
Để 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
-
Định nghĩa một hàm dfs (), hàm này sẽ lấy nút, c khởi tạo nó bằng 1,
-
nếu nút là null, thì -
-
trở lại
-
-
nếu c> lvl, thì -
-
lvl:=c
-
chèn giá trị của nút vào ret
-
-
dfs (bên trái của nút, c + 1)
-
dfs (bên phải của nút, c + 1)
-
Từ phương thức chính, thực hiện như sau -
-
lvl:=-1
-
dfs (gốc, 0)
-
trả lại ret
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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 = right = NULL;
}
};
class Solution {
public:
vector <int> ret;
int lvl;
void dfs(TreeNode* node, int c = 1){
if(!node)
return;
if(c > lvl){
lvl = c;
ret.push_back(node->val);
}
dfs(node->left, c + 1);
dfs(node->right, c + 1);
}
vector<int> solve(TreeNode* root) {
lvl = -1;
dfs(root, 0);
return ret;
}
};
main(){
TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->right = new TreeNode(5);
root->right->right = new TreeNode(4);
Solution ob;
print_vector(ob.solve(root));
} Đầu vào
TreeNode *root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->right = new TreeNode(5); root->right->right = new TreeNode(4);
Đầu ra
[1,2,5]