題目傳送門：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;}新聞熱點
疑難解答
