复习版
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* ======================================= COMMON ======================================= */
#define not !
#define and &&
#define or ||
#define ri register int
#define rep(inc, frm, to) for (ri inc = frm; inc < (to); ++inc)
#define rep2(inc, frm, to) for (ri inc = frm; inc > (to); --inc)
#define setbit(x, y) x |= 1 << y
#define clrbit(x, y) x &= ~(1 << y)
#define getbit(x, y) x >> y & 1
#define flipbit(x, y) x ^= 1 << y
#define show_bin(x) { rep2(i, 31, ~0) printf("%d%c", getbit(x, i), i ? 0 : 10); }
#define min(a, b) (a < b ? a : b)
#define max(a, b) (a > b ? a : b)
#define SWAP(a, b) { typeof(a) tmp = a; a = b; b = tmp; }
typedef long long int ll;
#define r() fast_read()
int is_digit(const char c) {
return c >= 48 and c <= 57;
}
ll fast_read(void) {
ll n = 0, sign = 1;
char c = getchar();
while (not is_digit(c)) {
if (c == '-') sign = ~0;
c = getchar();
}
while (is_digit(c)) {
n = (n << 1) + (n << 3) + (c ^ 48);
c = getchar();
}
return sign * n;
}
/* ======================================= COMMON ======================================= */
/* ======================================= SqQueue ======================================= */
#define Q_DEFAULT_CAPA 5
typedef int QElemType;
typedef struct {
QElemType* base;
int front, rear, capacity;
} SqQueue;
int InitQueue(SqQueue *Q, const int capacity) {
if (capacity <= 0) return 0;
Q->base = (QElemType*) malloc((capacity + 1) * sizeof(QElemType));
if (!Q->base) {
fprintf(stderr, "Failed to allocate the memory!\n");
return 0;
}
Q->front = Q->rear = 0;
Q->capacity = capacity + 1;
return 1;
}
int QueueEmpty(SqQueue *Q) {
return Q->front == Q->rear;
}
int QueueFull(SqQueue *Q) {
return (Q->rear + 1) % Q->capacity == Q->front;
}
int QueueLength(SqQueue *Q) {
return (Q->rear - Q->front + Q->capacity) % Q->capacity;
}
QElemType GetFront(SqQueue *Q) {
if (QueueEmpty(Q)) {
fprintf(stderr, "The queue is empty!\n");
return -1;
}
return *(Q->base + Q->front);
}
QElemType GetRear(SqQueue *Q) {
if (QueueEmpty(Q)) {
fprintf(stderr, "The queue is empty!\n");
return -1;
}
return Q->base[(Q->rear - 1 + Q->capacity) % Q->capacity];
}
int EnQueue(SqQueue *Q, QElemType *e) {
if (QueueFull(Q)) {
fprintf(stderr, "The queue is full!\n");
return 0;
}
*(Q->base + Q->rear) = *e;
Q->rear = (Q->rear + 1) % Q->capacity;
return 1;
}
int DeQueue(SqQueue *Q, QElemType *e) {
if (QueueEmpty(Q)) {
fprintf(stderr, "The queue is empty!\n");
return 0;
}
*e = *(Q->base + Q->front);
Q->front = (Q->front + 1) % Q->capacity;
return 1;
}
int QueuePop(SqQueue *Q) {
if (QueueEmpty(Q)) {
fprintf(stderr, "The queue is empty!\n");
return 0;
}
Q->front = (Q->front + 1) % Q->capacity;
return 1;
}
void CleanQueue(SqQueue *Q) {
Q->front = Q->rear = 0;
}
void DestroyQueue(SqQueue *Q) {
free(Q->base);
}
/* ======================================= SqQueue ======================================= */
#define MAX_N 12
typedef struct TNode TNode;
struct TNode {
int l_ch, r_ch;
} tree[MAX_N];
int n, rt = -1, has_parent[MAX_N];
void print_tree(void) {
putchar(10);
rep(i, 0, n) printf("%d %d %d\n", i, tree[i].l_ch, tree[i].r_ch);
}
int invert(int rt) {
if (rt == -1) return rt;
tree[rt].l_ch = invert(tree[rt].l_ch);
tree[rt].r_ch = invert(tree[rt].r_ch);
tree[rt].l_ch ^= tree[rt].r_ch;
tree[rt].r_ch ^= tree[rt].l_ch;
tree[rt].l_ch ^= tree[rt].r_ch;
return rt;
}
void print_node(int rt) {
putchar(rt | 48), putchar(32);
}
void level_order(void) {
SqQueue Q;
InitQueue(&Q, Q_DEFAULT_CAPA);
EnQueue(&Q, &rt);
int cur;
while (not QueueEmpty(&Q)) {
size_t sz = QueueLength(&Q);
while (sz--) {
DeQueue(&Q, &cur);
printf("%d ", cur);
if (tree[cur].l_ch != -1) EnQueue(&Q, &tree[cur].l_ch);
if (tree[cur].r_ch != -1) EnQueue(&Q, &tree[cur].r_ch);
}
}
DestroyQueue(&Q);
putchar(10);
}
void inorder(int rt, void (*visit) (int)) {
if (rt == -1) return;
inorder(tree[rt].l_ch, visit);
visit(rt);
inorder(tree[rt].r_ch, visit);
}
signed main(int argc, char const *argv[]) {
// freopen("test.in", "r", stdin);
memset(tree, ~0, sizeof tree); // default value: -1
n = r();
char lch, rch;
rep(i, 0, n) {
scanf("%c %c ", &lch, &rch);
if (lch != '-') {
(tree + i)->l_ch = lch ^ 48;
*(has_parent + (lch ^ 48)) = 1;
}
if (rch != '-') {
(tree + i)->r_ch = rch ^ 48;
*(has_parent + (rch ^ 48)) = 1;
}
}
while (has_parent[++rt]);
rt = invert(rt);
level_order();
inorder(rt, print_node);
// fclose(stdin);
return 0;
}
完全根据题意来模拟!
#include <iostream>
#include <queue>
using namespace std;
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* buildTree(vector<pair<int, int>>& data, int rootIdx) {
if (rootIdx == -1) return nullptr;
auto root = new TreeNode(rootIdx);
root->left = buildTree(data, data[rootIdx].first);
root->right = buildTree(data, data[rootIdx].second);
return root;
}
TreeNode* invertTree(TreeNode* root) {
if (!root) return nullptr;
root->left = invertTree(root->left);
root->right = invertTree(root->right);
swap(root->left, root->right);
return root;
}
void inOrder(TreeNode* root, vector<int>& ans) {
if (!root) return;
inOrder(root->left, ans);
ans.emplace_back(root->val);
inOrder(root->right, ans);
}
void levelOrder(TreeNode* root, vector<int>& ans) {
if (!root) return;
queue<TreeNode*> q{{root}};
while (not q.empty()) {
auto cur = q.front(); q.pop();
ans.emplace_back(cur->val);
if (cur->left) q.emplace(cur->left);
if (cur->right) q.emplace(cur->right);
}
}
const int N = 15;
int hasParent[N];
int n;
int main() {
scanf("%d", &n);
vector<pair<int, int>> data(n);
for (int i = 0; i < n; ++i) {
char l, r;
cin >> l >> r;
if (isdigit(l)) hasParent[l - '0'] = 1;
data[i].first = isdigit(l) ? l - '0' : -1;
if (isdigit(r)) hasParent[r - '0'] = 1;
data[i].second = isdigit(r) ? r - '0' : -1;
}
int rootIdx = -1;
for (int i = 0; i < n; ++i) {
if (!hasParent[i]) {
rootIdx = i;
break;
}
}
auto root = buildTree(data, rootIdx);
root = invertTree(root);
vector<int> v1, v2;
levelOrder(root, v1);
inOrder(root, v2);
for (const auto& x : v1) cout << x << ' ';
cout << endl;
for (const auto& x : v2) cout << x << ' ';
cout << endl;
return 0;
}
写的太棒了,感谢
very standard!