树-根据前序、中序遍历求后续遍历

题目要求 03-树3 Tree Traversals Again (25分)分析 我刚开始的想法是直接根据给出的操作构建相应的树，然后后序遍历即可。我的方法一代码（java版） import java.util.*; class Tree{ public int left = -1; //-1 means null public int right = -1; } public class Tree3 { public static Tree[] tree = new Tree[31]; public static boolean flag = false; //后序遍历 public static void postorderTraversal(int t){ if(t == -1) return; if(tree[t].left != -1){ postorderTraversal(tree[t].left); } if(tree[t].right != -1){ postorderTraversal(tree[t].right); } if(!flag){ System.out.print(t); flag = true; }else { System.out.print(" "+t); } } public static void main(String[] args) { Stack<Integer> stack = new Stack<Integer>(); for(int i=0; i<31; i++){ tree[i] = new Tree(); } Scanner in = new Scanner(System.in); int N = in.nextInt(); String line = null; int nowNode = -1, root = -1; boolean getRoot = false; in.nextLine();//注意这儿需要多加一个nextLine()来跳过第一行 for(int i=1; i<=2*N; i++){ line = in.nextLine(); if(line.startsWith("Push")){ if(!getRoot){//没有根的话，肯定先是构造根结点 nowNode = Integer.parseInt(line.split(" ")[1]); root = nowNode; getRoot = true; }else {//有根的话，push进来的必然是某个结点的子树 int tmp = Integer.parseInt(line.split(" ")[1]); if(tree[nowNode].left == -1){ tree[nowNode].left = tmp; }else { tree[nowNode].right = tmp; } nowNode = tmp; } stack.push(nowNode); }else { nowNode = stack.pop(); } } //后序遍历 postorderTraversal(root); System.out.println(); } }

这样的代码是正确的，但是需要操作比较小心，而且这是凭自己的感觉来做的，我不太能解释清楚这样为什么是对的，虽然最后也通过了，但我感觉这不是一个完美的方法。所以我就百度了一下，发现更好的方法是这样： 其实push的顺序就是这棵树的前序遍历的顺序，pop的顺序就是中序遍历的顺序。那么这道题便转化为了已知前序、中序遍历，求后序遍历。这个函数只需要递归求解就可以了。 - 我的方法二代码 （C++版）

#include <iostream> #include <stack> using namespace std; const int maxn = 31; stack<int> s; //保存前序、中序、后序遍历的顺序的数组 int preOrder[maxn],inOrder[maxn],postOrder[maxn]; void getPostOrder(int i,int j,int k,int n){ if(n == 0) return; //在前序遍历数组上找到根结点root int root = preOrder[i]; postOrder[k+n-1] = root;//把root放在后序遍历数组上相应的位置 //在中序遍历数组上找到根结点的位置 int index; for(index=j; index<j+n; index++){ if(inOrder[index] == root){ break; } } //求左右子树的长度 int L = index-j,R = j+n-index-1; //递归求解 getPostOrder(i+1, j, k, L);//处理左子树 getPostOrder(i+L+1, j+L+1, k+L, R);//处理右子树 } int main(int argc, const char * argv[]) { int N,x; int index1 = 1, index2 = 1; //preOrder[],inOrder[]的下标，从1开始 string op; cin>>N; //根据输入得到前序、中序遍历的顺序 for(int i=1; i<=2*N; i++){ cin>>op; if(op.compare("Push") == 0){ cin>>x; s.push(x); preOrder[index1++] = x; }else{ inOrder[index2++] = s.top(); s.pop(); } } //求后序遍历 getPostOrder(1, 1, 1, N); //输出 cout<<postOrder[1]; for(int i=2; i<=N; i++){ cout<<" "<<postOrder[i]; } cout<<endl; return 0; }