Giả sử chúng ta có một cây nhị phân. Chúng ta phải đi qua cây này bằng cách sử dụng thời trang duyệt thứ tự cấp độ. Vì vậy, nếu cây như
Trình tự duyệt sẽ như sau:[1,2,3,5,4]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
xác định hàng đợi để lưu trữ các nút
-
chèn root vào hàng đợi.
-
trong khi hàng đợi không trống, thực hiện
-
item:=item có mặt ở vị trí phía trước của hàng đợi
-
in giá trị của mặt hàng
-
nếu bên trái của mục không rỗng, thì hãy chèn bên trái của mục vào hàng
-
nếu bên phải của mục không rỗng, thì hãy chèn bên phải của mục vào hàng
-
xóa phần tử phía trước khỏi hàng đợi
-
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> solve(TreeNode* root) {
if(!root)
return {};
vector <int> ret;
queue <TreeNode*> q;
q.push(root);
while(!q.empty()){
TreeNode* node = q.front();
q.pop();
ret.push_back(node->val);
if(node->left){
q.push(node->left);
}
if(node->right){
q.push(node->right);
}
}
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, 3, 5, 4, ]