1138 Postorder Traversal (25 分)

---

填坑

---

#include<iostream> #include <bits/stdc++.h> using namespace std; const int maxn = 50000 + 10; int n; int pre[maxn]; int in[maxn]; int posttravel(int preL, int preR, int inL, int inR) { if(inL == inR) return in[inL]; int root = preL; //前序遍历的第一个节点为根节点 int i; for(i = inL; i <= inR; i++){ if(in[i] == pre[root]) break; //找到中序遍历中根基诶单的位置 } int numLeft = i - inL; //左子树的个数 if(numLeft == 0) //左子树不为空递归左子树；否则递归右子树 return posttravel(preL + 1 + numLeft, preR, i + 1, inR); else return posttravel(preL + 1, preL + numLeft, inL, i - 1); } int main() { 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]); printf("%d", posttravel(0, n - 1, 0, n - 1)); return 0; } /* 1 2 3 4 5 6 7 2 3 1 5 4 7 6 */