衛星

說明

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

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

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

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

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

  a
 / \
i   x
   / \
  f   r

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