POJ 2255 Tree Recovery

想法：
　　原本的字串是整棵Tree，我們可先找到這個Tree的Root，再將其分為左右Sub Tree，一直遞迴下去直到Sub Tree只剩一個元素。
　　具體做法是：

1. 先用Preorder String找出Root(P_root)，再透過P_root找到Inorder String的Root(I_root)
2. 然後用I_root分別找出左右Sub Tree在Inorder String的左右界(會有4個index：左子樹的左右界和右子樹的左右界)，再用剛才4個index的結果來找出左右子樹在Preoder String的左右界(一樣有4個index)。
3. 依照Post Order的順序：
1. 先遞迴左子樹
2. 再遞迴右子樹
3. 輸出Root

底下有附詳細註解的Code：

UVa 12347 Binary Search Tree

想法：
    真的直接造出一棵樹來~

UVa 10821 Constructing BST

想法：
    在最上層的時候，假設我們有數列{1,2,3,4,5,6,7}，要選出一個數字當作該層的root，例如選擇'4'，那麼{1,2,3}就被分配到左子樹，{4,5,6}到右子樹，到下一層我們一樣從{1,2,3}和{4,5,6}選出各自的root，然後繼續到下一層。
    但題目有說輸出要盡可能小，所以選擇root的時候，要盡可能選靠左邊的數字，所以要讓右子樹填滿，例如現在最上層數列為{1,2,3,4,5,6}，深度H=3，代表子樹深還有2，則左右子樹各別能提供(2^2-1=3)3個空間，因此我們選擇'3'當作root，分成{1,2}和{4,5,6}到左右子樹，讓右子樹3個空間被填滿，一直遞迴下去直到分配完全部數字。

UVa 712 S-Trees

題意：
    第一個數字為樹的深度N，然後有N個xi表示從root到(N-1)每一層的變數xi(例如x3 x1 x2表示root層的變數為x3，第1層變數為x1，第二層變數為x2)，接下來一串0和1的序列代表樹的最底層從左到右的値，然後有M個VVL，每個VVL依序表示變數xi的値(例如011表示x1=0，x2=1，x3=1)，因此知道xi代表的値後，就能從root走到底層(每層有自己的變數xi，遇到0向左走，1向右走)，一直走到底層看最底層是什麼數字。

想法：
    從root開始往下走，先將root編號n為0，往左下走就乘以2，往右下走就乘以2加1，直到最底層，看編號n是多少就輸出底層序列的第n個數字。
        0              root
    0       1          第1層
  0   1   2   3        第2層
 0 1 2 3 4 5 6 7       最底層

UVa 10666 The Eurocup is Here!

題意：

• Team 4贏過Team 6，而Team 6贏過Team 7，那麼表示Team 4確定贏過(優於)Team 7，也可說Team 7比Team 4差。
• Team 0同時贏過Team 4和Team 2，則Team 4和Team 2關係無法確定。
• 因為隊伍與隊伍之間關係有些確定有些不確定，本題要求出Team X可能最佳為第幾名，以及最差為第幾名

想法：

• 1.找最佳：只要找到贏過Team X的共有n隊，那麼n+1即是Team X的最佳名次。
• 1.做法：win(x)函數找到贏過Team X的隊伍(設為a)，再繼續win(a)找到贏過Team a的隊伍(設為b)，一直找到底(Team 0)為止，計算途中總共幾隊。
• 2.找最差：計算比Team X差的隊伍總共有幾隊，那麼Team X的最差名次就是全部隊伍數減掉比Team X還差的隊伍數
• 2.做法：Team X如果在Round r輸掉，那麼比Team X差的隊伍數為(2^(r-1)-1)，可多次觀察樹狀圖r=1,2,3,4...其結果為0,1.3,7...得知