题目描述
有序的二叉树遍历可以用堆栈以非递归的方式实现。
例如：
假设遍历一个节点数为6的二叉树（节点数据分别为1到6）时，
堆栈操作为：push（1）；push（2）；push（3）；pop（）；pop（）；push（4）；pop（）；pop（）；push（5）；push（6）；pop（）；pop（）。
外面可以根据这一操作序列生成一个唯一的二叉树。
我们的任务就是根据给出的操作序列求出该树的后序遍历序列；
换句话说，就是我们之前学习过的，根据给出先序遍历和中序遍历求出该树的后序遍历序列。
输入示例
第一行包含一个正整数N（≤30），它表示树中节点的总数。
接下来的2N行，每行描述一个堆栈操作，
格式为：“Push X”，其中X是被入到堆栈上的节点；
或“Pop”，意思是从堆栈中弹出一个节点。
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
解题思路
解这道题的思路并不难，我们之前就学习过通过两种遍历序列（其中一种为中序序列）就可以确定一颗唯一确定的二叉树，进而得到其余的遍历序列。即先序遍历序列中，第一个节点为根节点；后序遍历序列中，最后一个节点为根节点；中序遍历序列中根节点左右的序列分别是其左右子树的节点。
二叉树的遍历 习题
解题方法（C语言）
void solve(int preL, int inL, int postL, int n) { if(n == 0) { return; } if(n == 1) { post[postL] = pre[preL]; return; } root = pre[preL]; post[postL + n - 1] = root; for (i = 0; i < n; i++) { if (in[inL + i] == root) break; } L = i; R = n - L - 1; solve(preL + 1, inL, postL, L); solve(preL + L + 1, inL + L + 1, postL + L, R); }
解析
首先讲一下各变量的含义：
root表示当前子树的根节点；
pre表示先序遍历序列；
post表示后序遍历序列；
in表示中序遍历序列；
L表示当前子树的左子树节点个数；
R表示当前子树的右子树节点个数。
序列我们当成一个数组，
preL表示当前子树在先序遍历序列中的起始位置的下标；
inL表示当前子树在中序遍历序列中的起始位置的下标；
postL表示当前子树在后序遍历序列中的起始位置的下标；
n表示当前子树的节点个数。
函数的流程：
如果当前子树节点个数为0，则直接返回，没有后序遍历序列；
如果当前子树节点个数为1，则将该节点加入到后序遍历序列中，并返回；
如果当前子树节点个数大于1，则取出当前子树的根节点root，（即先序遍历序列的第一个元素）
将其加入到后序遍历序列的最后一个位置；（后序遍历序列中，最后一个元素为根节点）
然后在中序遍历序列中找到root的位置，将其左边的节点个数记为L，右边的节点个数记为R；
最后就是两个递归：
递归处理左子树，起始位置分别为preL+1、inL、postL，节点个数为L；
递归处理右子树，起始位置分别为preL+L+1、inL+L+1、postL+L，节点个数为R。
