PAT甲级-1086 Tree Traversals Again

题目

题目大意

题目给出二叉树的节点个数，并给出用栈遍历树的过程。要求输出树的后序遍历，不能有多余空格。

思路

可以看出，栈遍历输出的是树的中序遍历，而依次push进栈的是先序遍历的顺序。题目要求后序，即已知先序和中序遍历，求后序遍历。

可以先依次遍历先序，例如从先序第一个值开始，然后遍历中序找到与先序第一个值相等的值，中序中的这个值是树的根，左边的各值是它的左子树，右边是它的右子树。接着轮到先序第二个值，在中序的左子树中找到和第二个值相等的值，这个值是左子树中的一个根节点，左边是它的左子树，右边是它的右子树，就有些递归的感觉了。

由中序的树到左子树再到左子树的左子树，树的范围在缩小，当缩小到仅剩一个值的时候，就可以将它插入到树中了。中序树的范围可以由两个指针ml，mr表示。

前面说先序依次遍历，但在中序树的范围缩小后，先序的遍历范围也在缩小，即要满足先序的遍历范围恰好覆盖中序树的所有节点，否则就会重复遍历。先序数的范围可以用两个指针bl，br表示。

这也就确定了递归函数中的参数，分别是根节点、ml、mr、bl、br。

知识点

C++中对象和指针的声明是不一样的。声明对象时会直接为其分配空间，而声明指针不会，需要用new来手动显式分配空间。

指针在使用前最好被初始化为nullptr。

代码

#include <iostream>
#include <vector>
#include <string>
#include <stack>
using namespace std;

struct node{
    int data;
    node *lchild, *rchild;
};

vector<int> bef;  // 前序遍历
vector<int> mid;  // 中序遍历
vector<int> aft;  // 后序遍历

void buildTree(node * &root, int bl, int br, int ml, int mr){
    if (bl > br || ml > mr){
        return;
    }else{
        int pos;
        for (int i = ml; i <= mr; i++){
            if (bef[bl] == mid[i]){
                pos = i;
                break;
            }
        }  // 找到根节点
        root = new node();  // 添加根节点，指针都要被显式的分配内存，对象是隐式分配的
        root->data = bef[bl];
        root->lchild = root->rchild = nullptr;
        buildTree(root->lchild, bl + 1, bl + (pos - ml), ml, pos - 1);  // 确定先序节点的遍历范围是从bl + 1到bl + pos - bl
        buildTree(root->rchild, bl + (pos - ml) + 1, br, pos + 1, mr);  // 从bl + pos - bl + 1到br
    }
}  // 由先序和中序构造二叉树

void traverseAfter(node * root){
    if (root == nullptr){
        return;
    }
    traverseAfter(root->lchild);
    traverseAfter(root->rchild);
    aft.push_back(root->data);
}  // 后序遍历

int main(){
    int n;
    cin >> n;
    stack<int> s;
    for (int i = 0; i < 2 * n; i++){
        string a;
        cin >> a;
        if (a[1] == 'u'){
            int num;
            cin >> num;
            bef.push_back(num);
            s.push(num);
        }else{
            mid.push_back(s.top());
            s.pop();
        }
    }

    node * root = nullptr;  // 声明二叉树的根节点并初始化
    buildTree(root, 0, n - 1, 0, n - 1);
    traverseAfter(root);
    for (int i = 0; i < n; i++){
        cout << aft[i];
        if (i != n - 1){
            cout << " ";
        }
    }
    cout << endl;

    return 0;
}