题目传送门：http://acm.hdu.edu.cn/showPRoblem.php?pid=1710
由先序和中序求后序，递归求解但不建树。
//二叉树的遍历#include <iostream>#include <cstdio>#include <cstring>using namespace std;//记录前序和中序int pre[1010], in[1010];int n;//递归，preid代表树的根在前序中的下标，inid代表当前树在中序遍历的起始点，len代表当前树的结点个数void createTree(int preid, int inid, int len){ if (len == 0) { return ; } int temp = pre[preid]; int shift;//左子树结点个数 for (shift = 0; inid + shift < len; ++ shift) { if (in[inid + shift] == temp) { break; } } //递归左子树 createTree(preid + 1, inid, shift); //递归右子树 createTree(preid + shift + 1, inid + shift + 1,len - shift - 1); //最后访问根节点 printf((len == n)?"%d/n":"%d ",temp);}int main(){ while (~scanf("%d",&n)) { for (int i = 0; i < n; ++i) { scanf("%d",&pre[i]); } for (int i = 0; i < n; ++i) { scanf("%d",&in[i]); } createTree(0,0,n); } return 0;}新闻热点
疑难解答
