#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
若玩家視角僅顯示「無重疊區域」,也可輸出所有不被遮蔽者
Related
In following homework: