复习版
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <errno.h>
#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 ? 9 : 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;
}
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode, *PtrToNode;
typedef PtrToNode SElemType;
typedef struct {
SElemType* base; /* 顺序栈的基地址 */
SElemType* top; /* 栈顶指针 */
size_t capacity;
} SqStack;
bool InitStack(SqStack* S, size_t capacity) {
if (capacity <= 0) return 0;
S->base = malloc(capacity * sizeof(SElemType));
if (!S->base) {
fprintf(stderr, "%s\n", strerror(errno));
return 0;
}
S->top = S->base;
S->capacity = capacity;
return true;
}
bool StackEmpty(SqStack* S) {
return S->top == S->base;
}
bool StackFull(SqStack* S) {
return S->top - S->base == S->capacity;
}
size_t StackLength(SqStack* S) {
return S->top - S->base;
}
/* 暂时没考虑扩容失败的情况 */
bool __large(SqStack* S, float factor) {
SElemType* new_base = malloc((S->capacity * factor) * sizeof(SElemType));
if (!new_base) {
fprintf(stderr, "%s\n", strerror(errno));
return false;
}
memcpy(new_base, S->base, S->capacity * sizeof(SElemType)); // 复制数据
free(S->base); // 释放旧空间
S->base = new_base;
S->top = new_base + S->capacity;
S->capacity *= factor;
return true;
}
bool Push(SqStack* S, SElemType e) {
if (StackFull(S)) {
const size_t before = S->capacity;
__large(S, 1.5);
printf("Success: 系统进行了扩容动作。【从%ld扩到%ld!】\n", before, S->capacity);
}
*S->top++ = e;
return true;
}
bool Pop(SqStack* S, SElemType* e) {
if (StackEmpty(S)) {
fprintf(stderr, "The stack is empty!\n");
return 0;
}
*e = *--S->top;
return true;
}
SElemType GetTop(SqStack* S) {
if (StackEmpty(S)) return NULL;
return *(S->top - 1);
}
void DestroyStack(SqStack* S) {
free(S->base);
S->base = S->top = NULL;
}
#define MAX_N 40
void postOrder(PtrToNode root) {
if (not root) return;
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->val);
}
signed main(int argc, char const *argv[]) {
// freopen("test.in", "r", stdin);
int n = r();
char op[5];
SqStack S;
InitStack(&S, MAX_N);
PtrToNode root = NULL, p;
rep(i, 0, n << 1) {
scanf("%s", op);
if (!strcmp(op, "Push")) {
PtrToNode node;
node = malloc(sizeof *node);
node->val = r();
node->left = node->right = NULL;
Push(&S, node);
if (!root) {
p = root = node;
continue;
}
if (!p->left) p = p->left = node;
else p = p->right = node;
} else {
Pop(&S, &p);
}
}
postOrder(root);
// fclose(stdin);
return ~~(0 ^ 0);
}
算法1:
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {};
TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {};
~TreeNode() {};
};
void printAns(vector<int>& ans) {
for (int i = 0; i < ans.size(); ++i) {
printf("%d", ans[i]);
if (i < ans.size() - 1) printf(" ");
}
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
function<TreeNode*(int, int, int)> construct = [&](int i, int j, int n) {
if (n <= 0) return (TreeNode*) nullptr;
if (n == 1) return new TreeNode(preorder[i]);
int k = j;
while (inorder[k] != preorder[i]) ++k;
const int l = k - j; // l == 左子树的长度 ...
auto root = new TreeNode(inorder[k]);
root->left = construct(i + 1, j, l);
root->right = construct(i + 1 + l, k + 1, n - l - 1);
return root;
};
return construct(0, 0, preorder.size());
}
void postOrder(TreeNode* root, vector<int>& ans) {
if (!root) return;
postOrder(root->left, ans);
postOrder(root->right, ans);
ans.emplace_back(root->val);
}
int n, x;
string op;
vector<int> preorder, inorder;
stack<int> stk;
int main(void) {
cin >> n;
for (int i = 0; i < n << 1; ++i) {
cin >> op;
int action = op == "Push" ? 0 : 1;
switch (action) {
case 0:
cin >> x;
stk.emplace(x);
preorder.emplace_back(x);
break;
case 1:
inorder.emplace_back(stk.top());
stk.pop();
break;
default:
throw "ERROR SHIT!!!";
break;
}
}
vector<int> ans;
postOrder(buildTree(preorder, inorder), ans);
printAns(ans);
}
算法2:
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int n;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {};
~TreeNode();
};
TreeNode* buildTree(const int n) {
TreeNode *root = nullptr, *cur = nullptr;
stack<TreeNode*> s;
string op;
int id;
for (int i = 0; i < n << 1; ++i) {
if (i == 0) { // must be push root node
cin >> op >> id;
root = new TreeNode(id);
s.emplace(root);
cur = root;
continue;
}
cin >> op;
if (op == "Push") {
cin >> id;
auto node = new TreeNode(id);
if (cur->left) cur->right = node;
else cur->left = node;
s.emplace(node);
cur = node;
} else {
cur = s.top();
s.pop();
}
}
return root;
}
void postOrder(TreeNode* root, vector<int>& ans) {
if (!root) return;
postOrder(root->left, ans);
postOrder(root->right, ans);
ans.emplace_back(root->val);
}
void printAns(vector<int>& ans) {
for (int i = 0; i < ans.size(); ++i) {
printf("%d", ans[i]);
if (i < ans.size() - 1) printf(" ");
}
}
int main(void) {
cin >> n;
auto root = buildTree(n);
vector<int> ans;
postOrder(root, ans);
printAns(ans);
}