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 - blbuildTree(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;
}