单词

implemented mplement的过去分词形式 实施 实行

non-recursive 非递归的

题目

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.

1628512653962.png

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.

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结尾无空行

思路：

这道题的关键是意识到用非递归方式模拟递归时，入栈的顺序就是先序遍历，出栈的方式就是中序遍历（为什么呢？我是猜的，但题解中也未有见证明）。

意识到这一点后，就比较直观了。中序+先序建树，然后后序遍历，输出结果，与1020如出一辙。

代码

#include <bits/stdc++.h>
using namespace std;

vector<int> preorder;
stack <int> mystack;
vector<int> inorder;
vector<int> res;

struct node {
    int leftchild;
    int rightchild;
}Node[100];

int create(int ps, int pe, int is, int ie) {
    if (ps > pe) return -1;
    int a = preorder[ps];
    int i;
    for (i = is; i < ie; i++) {
        if (inorder[i] == a) break;
    }
    int numleft = i - is;
//  cout<<a<<" "<<numleft<<endl;
    Node[a].leftchild = create(ps + 1, ps + numleft, is, is + numleft - 1);
    Node[a].rightchild = create(ps + numleft + 1, pe, is + numleft + 1, ie);
    return a;
}

void postorder(int root) {
    if (root == -1) return;
    postorder(Node[root].leftchild);
    postorder(Node[root].rightchild);
    res.push_back(root);
    return;
}

int main() {
    int num;
    cin>>num;
    getchar();
    string str;
    for (int i = 0; i < 2 * num; i++) {
        getline(cin, str);
        if (str.size() > 4) {
            string num = str.substr(5);
            int a = 0;
            for (int j = 0; j < num.size(); j++) {
                a *= 10;
                a += num[j] - '0';
            }
            preorder.push_back(a);
            mystack.push(a);
        } else{
            int b = mystack.top();
            mystack.pop();
            inorder.push_back(b);
        }
    }
    int root = create(0, num-1, 0, num-1);
    postorder(root);
    for (int i = 0; i < num; i++) {
        cout<<res[i];
        if (i != num - 1) cout<<" ";
    }
}