第三周 树

主要讲的是二叉树[静态二叉树，不进行删除、增加]的存储结构与遍历方式。
存储结构比较简单，还是按照Node的思想，一个Node包含自身的item，以及左子树与右子树的指向。
遍历方式：

1. 前序、中序、后序【Print Left Right这三者的先后关系区分，主要可以利用迭代函数实现，或者递归地使用Stack】；
2. 层序遍历【利用Queue可以递归地实现，首先，把根节点入队，然后开始做循环（出队，讲左右子树入队，直到队列为空）】

题1：树的同构

给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。

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

解题思路：

1. 题目本身有点难理解，仔细看过以后，就是说一种对stack的操作，能够遍历一棵树。发现push的顺序就是前序访问的顺序，pop的顺序结果就是中序访问的结果。通过前序+中序，我们是可以得到后序的结果的。
2. 利用前序确定根节点，结合中序确定左子树的范围和右子树的范围。
3. 循环迭代，直到前序读取完全。

import java.util.Scanner;
import java.util.Stack;
import java.util.Arrays;

public class PostOrder {
    
    private static int[] result;    // postOrder;
    private static int[] advOrder;  // advOrder;
    private static int[] midOrder;  // midOrder;
    private static int N;           // number of nodes;
    
    public static void setPostOrder(int advLeft, int midLeft, int postLeft, int numNode) {
        // postLeft for postOrder; midLeft for # of midOrderHaveProcess; advLeft for # of rootHaveProcessed
        if (numNode == 0 || advLeft >= N)
            return;
        if (numNode == 1) {
            result[postLeft] = advOrder[advLeft];
            return;
        }
        
        int root = advOrder[advLeft];
        result[postLeft + numNode - 1] = root;
        int i;
        for (i = 0; i < numNode; i++) {
            if (midOrder[midLeft+i] == root)
                break;
        }
        
        setPostOrder(advLeft+1, midLeft, postLeft, i);                     // process left tree;
        setPostOrder(advLeft+i+1, midLeft+i+1, postLeft+i, numNode-i-1);   // process right tree;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String inputLine = new String();
        while (in.hasNext()) {
            N = in.nextInt();
            in.nextLine();
            int numPop = 0;     // number of pop operation;
            int numPush = 0;    // number of push operation;
            Stack<Integer> st = new Stack<Integer>();
            advOrder = new int[N];
            midOrder = new int[N];
            for (int i = 0; i < 2*N; i++) {
                inputLine = in.next();
                if (inputLine.substring(0,3).equals("Pop")) {
                    midOrder[numPop++] = st.pop();
                }
                    
                else {
                    advOrder[numPush++] = in.nextInt();
                    st.push(advOrder[numPush-1]);
                }
                in.nextLine();
            }

            result = new int[N];
            PostOrder.setPostOrder(0,0,0,N);
            
            String rsstr = String.valueOf(result[0]);
            for (int i = 1; i < N; i++) {
                rsstr += " " + String.valueOf(result[i]);
            }
            System.out.println(rsstr);
        }
    } 
}