03-树3 Tree Traversals Again（25 分）

题目

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:

6Push 1Push 2Push 3PopPopPush 4PopPopPush 5Push 6PopPop

Sample Output:

3 4 2 6 5 1

思路

1） 通过 输入的 push 顺序，得到前序遍历的数组

2）通过 push 和 pop 得到 中序遍历的数组

3）通过前序和中序的数组，可以唯一确定一个后序遍历数组。

代码

import java.util.*;class TreeNode1{    int val;    int left;    int right;}/** * 拥有前序和中序，需要后序遍历结点 */public class Main {
     //    public static int[] in ={};//    int[] pre ={};    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        int N =sc.nextInt();      //  int root =buildTree(sc,N,T1);        //list 中第一个为前序，第二个为中序，需要打印的是后序遍历的结果        List
     
      
       > list = buildTree(sc,N);        list.get(0);        int[] pre = new int[list.get(0).size()];        int[] in  = new int[list.get(1).size()];        for (int i=0;i
       
         res = new ArrayList<>();        post(0,0,in.length-1,in,pre,res);        //System.out.println();        for (int i=0;i
        
         > buildTree(Scanner sc, int N){        Stack
         
           stack = new Stack<>();//构建一个堆        List
          
            preOrderTrav = new ArrayList<>(); List
           
             middleOrder = new ArrayList<>(); for (int i=0;i<2*N;i++){ String str = sc.next(); if (str.equals("Push")){ int num = sc.nextInt(); stack.push(num); preOrderTrav.add(num); } else { int num = stack.pop(); middleOrder.add(num); } } List
            
             
              > res = new ArrayList<>(); res.add(preOrderTrav); res.add(middleOrder); return res; } /** * https://blog.csdn.net/liuchuo/article/details/52135882 * @param root * @param start * @param end * @param in * @param pre * @param res * @return */ public static List
              
                post(int root, int start, int end,int [] in,int []pre,List
               
                 res) { if(start > end) return null; int i = start; while(i < end && in[i] != pre[root]) i++; post(root + 1, start, i - 1,in,pre,res); post(root + 1 + i - start, i + 1, end,in,pre,res); res.add(pre[root]); //System.out.println(pre[root]); return res; }}