题目描述：
An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.
Figure 1
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: “Push X” where X is the index of the node being pushed onto the stack; or “Pop” meaning to pop one node from the stack.
Output Specification:
For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input:
6 Push 1 Push 2 Push 3 Pop Pop Push 4 Pop Pop Push 5 Push 6 Pop Pop
Sample Output:
3 4 2 6 5 1
解题思路：
通过题目可以发现push是先序遍历，pop是中序遍历，然后根据先序和中序构造树，后序遍历出结果。
代码：
package text2; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Stack; public class TreeTraversalsAgain { static ArrayList<Integer> post = new ArrayList<>(); public static void main(String[] args) throws NumberFormatException, IOException { // TODO Auto-generated method stub BufferedReader read = new BufferedReader(new InputStreamReader(System.in)); int n=Integer.parseInt(read.readLine()); int pre[] = new int[n]; int in[] = new int[n]; Stack<Integer> stack = new Stack<>(); for(int i=0,j=0,k=0;i<2*n;i++) { String[] str = read.readLine().split(" "); if(str[0].equals("Push")) {//前序 pre[j]=Integer.parseInt(str[1]); stack.push(pre[j]); j++; }else { in[k]=stack.pop(); k++; } } Node root = buildTree(pre, 0, n-1, in, 0, n-1); PrintPost(root); // System.out.println(post.size()); for(int i=0;i<post.size();i++) { if(i==0) System.out.print(post.get(i)); else System.out.print(" "+post.get(i)); } } //根据前序与中序创建二叉树模板 public static Node buildTree(int pre[],int pbegin,int pend,int in[],int ibegin,int iend) { if(pbegin>pend||ibegin>iend) return null; Node root = new Node(pre[pbegin]);//根节点 for(int i=ibegin;i<=iend;i++) { if(pre[pbegin]==in[i]) { root.left = buildTree(pre, pbegin+1, pbegin-ibegin+i, in, ibegin, i-1); root.right = buildTree(pre, pbegin-ibegin+i+1, pend, in, i+1, iend); } } return root; } //后序遍历 public static void PrintPost(Node root) { if(root!=null) { PrintPost(root.left); PrintPost(root.right); post.add(root.element); } } } class Node{ //树节点类 public int element; //节点值 public Node left; //左右节点 public Node right; public Node(int element) { // TODO Auto-generated constructor stub this.element = element; left = right = null; } }
