衛星

說明

想像一下，你需要把一棵二元樹傳送到正在接近 Alpha Centauri 的衛星上，而你的頻寬有限。 這棵樹沒有重複的項目，因此可以由它的前序與中序走訪唯一表示。

請為衛星撰寫軟體，根據這些走訪結果重建這棵樹。

前序走訪會先讀取目前節點的值（因此稱為「pre」），再以前序走訪左子樹。 接著同樣以前序走訪右子樹。

中序走訪會先以中序走訪左子樹，再讀取目前節點，最後以中序走訪右子樹。 也就是由左到右的順序。

例如，這棵樹的前序走訪是 [a, i, x, f, r]。 這棵樹的中序走訪是 [i, a, f, x, r]

  a
 / \
i   x
   / \
  f   r

注意：前序走訪中的第一個項目永遠是根節點。

例外訊息

有時候，你需要引發例外。這麼做時，你應該一律附上有意義的錯誤訊息，指出錯誤的來源是什麼。這能讓你的程式碼更好讀，對除錯也有很大的幫助。如果你知道錯誤來源會是某種特定類型，可以選擇引發其中一種內建的錯誤類型，但還是應該附上有意義的訊息。

這個練習要求你使用raise 敘述來「拋出」ValueError，前提是 preorder和inorder這兩個引數的長度不符、元素不符，或是元素不唯一。只有在同時 raise exception 並附上訊息時，測試才會通過。

若要引發帶有訊息的 ValueError，請把訊息寫成 exception型別的引數：

# if preorder and inorder are not the same length
raise ValueError("traversals must have the same length")

# if preorder and inorder do not share the same elements
raise ValueError("traversals must have the same elements")
    
# if element repeat (are not unique)    
raise ValueError("traversals must contain unique items")