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 = -) :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 + , preL + k, ordL, ordL + k - );//构造左子树

     root->r = Create(dataPre, dataOrd, preL + k + , preR, ordL + k + , 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 =  * 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, , dataPre.size() - , , dataOrd.size() - );

     vector<int>res;

     LastTravle(res, root);

     for (int i = ; i < res.size() - ; ++i)

         cout << res[i] << " ";

     cout << res[res.size() - ] << 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 + , start, i - );

     postorder(root +  + i - start, i + , end);

     post.push_back(pre[root]);

 }

 int main() {

     int n;

     cin >> n;

     n =  * n;

     stack<int> s;

     int key = ;

     while (n--) {

         string str;

         cin >> str;

         if (str.length() == ) {

             int num;

             cin >> num;

             value.push_back(num);

             pre.push_back(key);

             s.push(key++);

         }

         else {

             in.push_back(s.top());

             s.pop();

         }

     }

     postorder(, , pre.size() - );

     printf("%d", value[post[]]);

     for (int i = ; i < n; i++)

         printf(" %d", value[post[i]]);

     return ;

 }

巴特西

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

题目描述

输入描述:

输出描述:

输入例子:

输出例子:

解题思路：

版本一：

版本二：

最新文章

热门文章