#LAISIR37. 棋盤之下 · 幻獸投影

棋盤之下 · 幻獸投影

🎲 題目名稱:棋盤之下 · 幻獸投影


📝 題目背景:

在奇幻桌遊《幻獸國度》中,每位玩家依照樹狀結構部署單位,這些單位從上往下堆疊在虛擬棋盤上。整個單位樹是由魔法網格支撐,並遵循一種特殊的排列規則:單位左連接表示佈置在左側網格、右連接表示右側。

玩家完成佈陣後,遊戲系統會自動產生地圖預覽——從下方觀察棋盤,每個網格位置只會顯示「被壓在最底層」的單位(也就是該橫向位置最後出現的節點)。

你作為系統後端的視覺渲染模組,需要根據玩家的樹形佈陣,輸出棋盤底下能看到的幻獸單位。


🎯 任務說明:

給定一棵玩家的單位樹,其先序遍歷(包含 "null" 表示空節點),請你輸出從棋盤下方觀察時,每個橫向位置上所能看到的單位編號。


📥 輸入格式:

第一行:一個整數 n(1 ≤ n ≤ 10^5),表示完全先序序列長度(包含 "null")

第二行:n 個字串,為先序遍歷序列
- 非空節點為整數(-10^5 到 10^5),代表幻獸單位編號
- 空節點為字串 "null"

📤 輸出格式:

一行輸出,為從下往上觀察所見的單位編號,依照橫向位置 x 從小到大排列,以空格分隔。


📘 輸入範例:

13
1 2 4 null null 5 null null 3 null 6 null null

📗 輸出範例:

4 5 6

🌳 樹形說明:

重建後的單位樹結構如下:

        1
      /   \
     2     3
    / \     \
   4   5     6

橫向座標(假設根節點 x=0):

  • 4 → x = -2
  • 2 → x = -1
  • 5 → x = 0
  • 1 → x = 0(但被 5 覆蓋)
  • 3 → x = 1
  • 6 → x = 2

對於每個 x,只輸出最後出現的節點

  • x=-2 → 4
  • x=-1 → 2
  • x= 0 → 5
  • x= 1 → 3
  • x= 2 → 6

所以輸出為:

4 2 5 3 6

若玩家視角僅顯示「無重疊區域」,也可輸出所有不被遮蔽者