PAT甲级——【牛客练习A1004】

题目描述

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.

Figure 1

输入描述:

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.

输出描述:

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.

输入例子:

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

输出例子:

3 4 2 6 5 1

解题思路：

根据题意可知， 栈的数据压入为二叉树的前序，栈的弹出为中序，求后序遍历
一般是通过前序、中序来构造二叉树，然后在遍历出后序遍历即可

版本一：

该版本的缺陷是，当出现相同数字时，无法在中序中确定谁是根节点！

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

struct Node
{
    int val;
    Node* l;
    Node* r;
    Node(int a = -1) :val(a), l(nullptr), r(nullptr) {}

};

//通过前序、中序构造二叉树
Node* Create(const vector<int>dataPre, const vector<int>dataOrd,
    int preL, int preR, int ordL, int ordR)//数据源，前序的左右边界，中序的左右边界
{
    if (preL < preR)
        return nullptr;
    Node* root = new Node();
    root->val = dataPre[preL];//根节点
    int k = ordL;
    while (dataOrd[k] != dataPre[preL])
        ++k;
    k = k - ordL;//左子树个数
    root->l = Create(dataPre, dataOrd, preL + 1, preL + k, ordL, ordL + k - 1);//构造左子树
    root->r = Create(dataPre, dataOrd, preL + k + 1, preR, ordL + k + 1, ordR);//构造右子树
    return root;
}

//后序遍历
void LastTravle(vector<int>&res, Node* root)
{
    if (root == nullptr)
        return;
    LastTravle(res, root->l);
    LastTravle(res, root->r);
    res.push_back(root->val);
}


int main()
{
    int N;
    cin >> N;
    N = 2 * N;
    stack<int>data;
    vector<int>dataPre, dataOrd;
    while (N--)
    {
        string str;
        cin >> str;
        if (str == "Push")
        {
            int a;
            cin >> a;
            dataPre.push_back(a);
            data.push(a);
        }
        else
        {
            dataOrd.push_back(data.top());
            data.pop();
        }
    }
    Node* root;
    root = Create(dataPre, dataOrd, 0, dataPre.size() - 1, 0, dataOrd.size() - 1);
    vector<int>res;
    LastTravle(res, root);
    for (int i = 0; i < res.size() - 1; ++i)
        cout << res[i] << " ";
    cout << res[res.size() - 1] << endl;
}

版本二：

使用key，避免了重复数字的尴尬，也不需真正构造一颗二叉树

#include <vector>
#include <stack>
#include <string>
using namespace std;
vector<int> pre, in, post, value;
void postorder(int root, int start, int end) {
    if (start > end) return;
    int i = start;
    while (i < end && in[i] != pre[root]) i++;
    postorder(root + 1, start, i - 1);
    postorder(root + 1 + i - start, i + 1, end);
    post.push_back(pre[root]);
}
int main() {
    int n;
    cin >> n;
    n = 2 * n;
    stack<int> s;
    int key = 0;
    while (n--) {
        string str;
        cin >> str;
        if (str.length() == 4) {
            int num;
            cin >> num;
            value.push_back(num);
            pre.push_back(key);
            s.push(key++);
        }
        else {
            in.push_back(s.top());
            s.pop();
        }
    }
    postorder(0, 0, pre.size() - 1);
    printf("%d", value[post[0]]);
    for (int i = 1; i < n; i++)
        printf(" %d", value[post[i]]);
    return 0;
}