03-树3 Tree Traversals Again

An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.

有序二叉树遍历可以用堆栈以非递归方式实现。例如，假设遍历6节点二叉树（键编号从1到6）时，堆栈操作为：push（1）；推（2）；推（3）；pop（）；pop（）；推动（4）；pop（）；pop（）；推（5）；推动（6）；pop（）；pop（）。然后，可以从这个操作序列中生成一个唯一的二叉树（如图1所示）。您的任务是给出此树的后序遍历序列。

Figure 1

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: "Push X" where X is the index of the node being pushed onto the stack; or "Pop" meaning to pop one node from the stack.

每个输入文件包含一个测试用例。对于每种情况，第一行包含正整数N(≤30），这是树中节点的总数（因此节点从1到N编号）。接下来是2N行，每行都以如下格式描述堆栈操作：“Push X”，其中X是被推到堆栈上的节点的索引；或“Pop”表示从堆栈中弹出一个节点。

Output Specification:

For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

对于每个测试用例，在一行中打印相应树的后序遍历序列。保证存在解决方案。所有的数字必须用一个空格隔开，并且行的末尾不能有多余的空格。

Sample Input:

6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop

Sample Output:

3 4 2 6 5 1

思路：

根据给定push，pop过程我们可以建一棵树，然后后序遍历

也可以根据push得出先序遍历，pop得出中序遍历，将问题转化为根据先序和中序求后序

当然，建树的都会了，不建树也可以啦

代码（建树然后后序遍历）：

#include 
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
struct Tree {
    int e;
    Tree* lchild, * rchild;
};
int i,n;
string s;
bool fg = true;
void Create(Tree*& t,int x) {
    t = (Tree*)malloc(sizeof(struct Tree));
    t->e = x;
    t->lchild = t->rchild = NULL;
}
void BuildTree(Tree*& t){
   // if (i == n)return ;
   // i++;
    cin >> s;
    if (s.size() == 4) {
        int x;
        cin >> x;
        Create(t, x);
    }
    else return;
    BuildTree(t->lchild);
    BuildTree(t->rchild);
}
void fun(Tree* t) {
    if (t == NULL)return;
    fun(t->lchild);
    fun(t->rchild);
    
    if (fg) {
        fg = false;
        cout << t->e ;
    }else cout <<" "<< t->e;
}
int main()
{
    cin >> n;
    Tree* t;
    BuildTree(t);
    fun(t);
    return 0;
}

代码（用先序序列和中序序列建树）：

#include 
using namespace std;
typedef pair<int, int> PII;
const int N = 35;
struct Tree {
    int e;
    Tree* lchild, * rchild;
};
int i, n;
string s;
vector<int> pre, in;
stack<int> stk;
bool fg = true;
void Create(Tree*& t, int x) {
    t = (Tree*)malloc(sizeof(struct Tree));
    t->e = x;
    t->lchild = t->rchild = NULL;
}
void BuildTree(Tree*& t, int root, int l, int r) {
    if (l > r)return;
    Create(t, pre[root]);
 
    int k = 0, i = l;
    for (; i <= r; i++)if (pre[root] == in[i])break;
    BuildTree(t->lchild, root + 1, l, i - 1);
    BuildTree(t->rchild, root + i - l + 1, i + 1, r);
}
 
void fun(Tree* t) {
    if (t == NULL)return;
    fun(t->lchild);
    fun(t->rchild);
 
    if (fg) {
        fg = false;
        cout << t->e;
    }
    else cout << " " << t->e;
}
int main()
{
    cin >> n;
    for (int i = 0; i < 2 * n; i++) {
        cin >> s;
        if (s.size() == 4) {
            int x;
            cin >> x;
            pre.push_back(x);
            stk.push(x);
        }
        else {
            in.push_back(stk.top());
            stk.pop();
        }
    }
    Tree* t;
 
    BuildTree(t, 0, 0, n - 1);
    fun(t);
    return 0;
}

代码（当然，不建树也可以啦）：

#include 
using namespace std;
typedef pair<int, int> PII;
const int N = 35;
 
int i, n;
string s;
vector<int> pre, in;
stack<int> stk;
bool fg = true;
vector<int> ans;
 
void Create_post(int root, int l, int r) {
    if (l > r)return;
    int res = root;
    int k = 0, i = l;
    for (; i <= r; i++)if (pre[root] == in[i])break;
    Create_post(root + 1, l, i - 1);
    Create_post(root + i - l + 1, i + 1, r);
    ans.push_back(pre[res]);
}
 
 
int main()
{
    cin >> n;
    for (int i = 0; i < 2 * n; i++) {
        cin >> s;
        if (s.size() == 4) {
            int x;
            cin >> x;
            pre.push_back(x);
            stk.push(x);
        }
        else {
            in.push_back(stk.top());
            stk.pop();
        }
    }
    Create_post(0, 0, n - 1);
 
    for (int i = 0; i < ans.size(); i++) {
        if (fg) {
            fg = false;
            cout << ans[i];
        }
        else cout << " " << ans[i];
    }
 
    return 0;
}