关于算法-数据结构:PAT甲级1086-Tree-Traversals-Again

题目粗心：

用栈来模仿一颗二叉树的先序和中序遍历过程, 求这课树的后序遍历序列。

算法思路:

首先得说一个论断, 就是栈的入栈序列就是一颗二叉树的先序遍历, 出栈序列就是一颗二叉树的中序遍历序列, 那么这个题目就转化为依据先序和中序求后序遍历序列。那么首先就是依据先序和中序建设二叉树，而后依据这个二叉树进行后序遍历取得后序遍历序列。

递归建设二叉树

假如递归过程中某步的前序区间是 $[beginPre,lastPre]$, 中序区间是 $[beginIn,lastIn]$, 那么根节点为 $pre[beginPre]$, 首先初始化根节点 $root$，接着须要在中序遍历中找到根节点的地位 $index_root$, 而后计算左子树的个数 leftTreeLen = index_root-beginIn; 这样左子树和右子树在后序和中序遍历中就离开了, 紧接着就是左子树递归:

root->left =createTree(beginPre+1,beginPre+leftTreeLen,beginIn,index_root-1);

右子树递归:

root->right = createTree(beginPre+leftTreeLen+1,lastPre,index_root+1,lastIn);

递归的边界 就是在区间长度小于 0 的时候间接返回空即可。

留神点：

• 1、输出的行数为 N 的 2 倍。

提交后果：

AC 代码：

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

using namespace std;

struct Node{
    int data;
    Node* left;
    Node* right;
};

int N;// 节点个数
vector<int> pre,In;

Node* createTree(int beginPre,int lastPre,int beginIn,int lastIn){if(beginPre>lastPre) return nullptr;
    // 初始化根节点
    Node* root = new Node;
    root->data = pre[beginPre];
    // 在中序序列
    int index_root;
    for(index_root=beginIn;index_root<=lastIn;++index_root){if(In[index_root]==root->data) break;
    }
    int leftTreeLen = index_root-beginIn;
    root->left = createTree(beginPre+1,beginPre+leftTreeLen,beginIn,index_root-1);
    root->right = createTree(beginPre+leftTreeLen+1,lastPre,index_root+1,lastIn);
    return root;
}

int num = 0;// 输入节点的个数，用来管制输入
void postTraverse(Node* root){if(root== nullptr) return;
    postTraverse(root->left);
    postTraverse(root->right);
    printf("%d",root->data);
    if(num<N-1) printf(" ");
    ++num;
}

int main()
{scanf("%d",&N);
    string s;
    int num;
    stack<int> st;
    // 输出的数据有 2 * N 行
    for (int i = 0; i < 2*N; ++i) {
        cin>>s;
        if(s=="Push"){scanf("%d",&num);
            st.push(num);
            pre.push_back(num);
        } else {num = st.top();
            st.pop();
            In.push_back(num);
        }
    }
    Node* root = createTree(0,N-1,0,N-1);
    postTraverse(root);
    return 0;
}