03-树3 Tree Traversals Again （25 分）

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.

二叉树

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

题目分析

给了中序的非递归遍历方法，求后序遍历的二叉树输出

我的答案

//
// Created by allenhsu on 2018/10/31.
//

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

using namespace std;
// 传入后序序列的引用 核心代码！
void getPostOrder(vector<int> preOrder, int preL, vector<int> inOrder, int inL, vector<int> &postOrder, int postL, int n){
    if (n == 0) return;
    if (n == 1){
        postOrder[postL] = preOrder[preL];
        return;
    }
    auto root = preOrder[preL];
    postOrder[postL + n - 1] = root;
    int i;  // 中序遍历的root位置
    for (i = 0; i < n; ++i) {
        if (inOrder[inL + i] == root) break;
    }
    int L = i, R = n - i - 1;
    getPostOrder(preOrder, preL + 1, inOrder, inL, postOrder, postL, L);
    getPostOrder(preOrder, preL + L + 1, inOrder, inL+L+1, postOrder, postL+L, R);
}

/**
 * 根据输入返回前序和中序遍历vertor
 * @param N 该二叉树的节点个数
 * @return 返回两个vertor序列
 */
vector<vector<int>> getOrder(int N){
    vector<int> preOrder(N, 0);
    vector<int> inOrder(N, 0);
    stack<int> s;
    int preL = 0, inL = 0;
    for (int i = 0; i < 2 * N; ++i) {
        string str;
        int tmp;
        cin >> str;
        if (str == "Push"){     // str可以直接比较
            cin >> tmp;
            s.push(tmp);
            preOrder[preL++] = tmp;
        } else if (str == "Pop"){
            inOrder[inL++] = s.top();   // top 返回栈顶元素
            s.pop();
        }
    }
    return {preOrder, inOrder};     // 返回数组vector
}

int main(){
    int N;
    cin >> N;
    auto order = getOrder(N);
    vector<int> postOrder(N,0); // 初始化动态数组要指明参数
    getPostOrder(order[0], 0, order[1], 0, postOrder, 0, N);

    int i = 0;
    for (; i < N - 1; ++i) {
        cout << postOrder[i] << " ";
    }
    cout << postOrder[i] << endl;
    return 0;
}

感悟

本次的作业自认为挺难的。我没有独立完成，是copy网上自己读懂后敲得。值得再回头多看几遍。核心函数getPostOrder(); 理解其中的递归求解思路。