链表
结合lc的链表结构体和遍历构造
#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(): val(0), next(nullptr) {}
ListNode(int val): val(val), next(nullptr) {}
ListNode(int val, ListNode *next): val(val), next(next) {}
};
ListNode* createListNode(int n) {
auto dummy = new ListNode(-1);
auto pre = dummy;
for (int i = 0; i < n; i ++ ) {
auto root = new ListNode(0);
cin >> root->val;
pre->next = root;
pre = pre->next;
}
return dummy->next;
}
int main() {
int n;
cin >> n;
auto root = createListNode(n);
//cout << root->val << endl;
return 0;
}
二叉树
测试数据
9
1 2 3 -2 -863843 4 5 7 8
使用层序遍历输出二叉树的结果
#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10;
int n;
vector<int> arr(N);
// new的时候只填val值,left&right指针默认置空
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int val, TreeNode *left = nullptr, TreeNode *right = nullptr) {
this->val = val,
this->left = left,
this->right = right;
}
};
TreeNode* createBiTree(vector<int>& arr, int u) {
if (u > n) return nullptr;
auto root = new TreeNode(arr[u]);
root->val = arr[u];
root->left = createBiTree(arr, 2 * u);
root->right = createBiTree(arr, 2 * u + 1);
return root;
}
queue<TreeNode*> q;
vector<vector<int>> res;
vector<int> ans;
vector<vector<int>> cengxu(TreeNode* root) {
q.push(root);
while (q.size()) {
int len = q.size();
for (int i = 0; i < len; i ++ ) {
auto t = q.front();
q.pop();
ans.push_back(t->val);
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
res.push_back(ans);
ans.clear();
}
return res;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> arr[i];
auto root = createBiTree(arr, 1);
// cout << root->left->val << endl;
res = cengxu(root);
for (int i = 0; i < res.size(); i ++ ) {
for (int j = 0; j < res[i].size(); j ++ )
cout << res[i][j] << ' ';
cout << endl;
}
return 0;
}