PAT甲级(Advanced Level)练习题——1004

Tree Traversals Again
给了一个模拟的二叉树非递归中序遍历push/pop序列，要求我们求出其后序遍历。

我的思路是这样的，先根据push/pop序列求出其先序遍历（即push的顺序）和中序遍历（即每次pop时候栈顶的值），再递归重建二叉树，最后再后序遍历即可。

#include <iostream>
#include <string>
#include <stack>

using namespace std;

struct BTNode   // tree node
{
    int data;
    BTNode *lchild, *rchild;
};

BTNode *reBuildTree (int preOrder[], int inOrder[], int n)
{
    if(n <= 0) return NULL;      // 左右子树的节点为0，即递归结束时，返回空指针

    BTNode *root = new BTNode;
    root->data = preOrder[0];    // 前序遍历的第一个元素是根节点的值

    int i = 0;
    for(; i<n; i++)
    {
        // 在中序遍历中寻找根节点的位置
        if(inOrder[i] == preOrder[0]) break;
    }

    // 在中序遍历中i左边的元素是左子树的中序遍历结果，右边的元素是右子树的中序遍历结果
    // 在前序遍历中根节点（preOrder[0]）之后的i个元素是左子树的前序遍历结果
    // 递归调用重建左右子树即可
    root->lchild = reBuildTree(preOrder+1, inOrder, i);  // 将数组名当指针使用
    root->rchild = reBuildTree(preOrder+1+i ,inOrder+i+1, n-i-1);
    return root;
}

void postorder(BTNode *root)
{
    if (root == NULL)
    {
        return;
    }
    postorder(root->lchild);
    postorder(root->rchild);
    cout << root->data << " ";
}

int main()
{
    freopen("input.txt", "r", stdin); //

    stack<int> i_stack;
    stack<int> pre_order, in_order;

    int s_number = 0;
    cin >> s_number;

    for (int i=0; i<2*s_number; i++) //记录先序遍历与中序遍历
    {
        string s_temp;
        cin >> s_temp;

        if (s_temp.at(1) == 'u')    // 字符串为"push"
        {
            int i_temp;
            cin >> i_temp;
            pre_order.push(i_temp); // 记录先序遍历
            i_stack.push(i_temp);       // 入栈
        }
        else
        {
            int i_temp = i_stack.top();
            i_stack.pop();              // 出栈
            in_order.push(i_temp);      // 记录中序遍历
        }
    }

    int *Pre_order  = new int[s_number];
    int *In_order  = new int[s_number];

    for (int i=s_number-1; i>=0; i--)    // 这里用数组比较方便，因为数组名可以当做指针使用，递归时可直接修改地址
    {
        Pre_order[i] = pre_order.top();
        In_order[i] = in_order.top();
        pre_order.pop();
        in_order.pop();
    }

    BTNode *BinaryTree = reBuildTree(Pre_order, In_order, s_number);
    postorder(BinaryTree);

    return 0;
}

// for (int i=num-1; i>=0; i--)
// for (int i=0; i<num; i++)
// 注意在index操作中这两个互为逆置等价

测试用例并没有问题，但是...在OJ上报错了，查看测试点发现测试数据给了许多重复值，如：

4
push 2
push 3
pop
push 1
pop
push 3
push 3
pop
pop
pop
push 4
pop

这就使得我在寻找根节点的位置这一步出错

后来参考了别人的代码

#include<cstdio>
#include<vector>
#include<algorithm>
 
using namespace std;
int n,cnt = 1;
char s[20];
vector<int> out;
struct node {
    int val;
    struct node *left, *right;
};
node* buildTree()  // 直接重建二叉树，先左后右，左边会一直深入，直到left == NULL，再转向right
{
    if (cnt < 2 * n) {
        scanf("%s", s);
        cnt++;
        if (s[1] == 'u') {
            int v;
            node* temp = new node();  
            scanf("%d",&v);
            temp->val = v;
            temp->left = buildTree();
            temp->right = buildTree();
            return temp;
        }
        else {
            return NULL;
        }
    }
    return NULL;
}
void post(node* root) {
    if (root->left != NULL) {
        post(root->left);
    }
    if (root->right != NULL) {
        post(root->right);
    }
    out.push_back(root->val);
}
int main() {
 
    scanf("%d", &n);
    node *root = NULL;
    root = buildTree();
    post(root);
    printf("%d", out[0]);
    for (int i = 1; i < n; i++) {
        printf(" %d", out[i]);
    }
    return 0;
}

顺利通过~