#LAISIR42. 古樹守望者的視角(Top View of Binary Tree)
古樹守望者的視角(Top View of Binary Tree)
🧭 題目名稱:古樹守望者的視角(Top View of Binary Tree)
📝 題目描述:
在一片神秘的森林中,存在一棵古老的二叉樹。每位守望者站在一個節點上,保衛著森林中的一個區域。
你現在站在這棵樹的正上方俯瞰整片森林,想知道有哪些守望者能被你看到。你只能看到在每個「水平座標」上,最先出現在視野中的那一位守望者。
我們定義節點的「水平距離(Horizontal Distance, HD)」如下:
- 根節點的 HD 為 0。
- 若某節點的 HD 為
d
,其左子節點的 HD 為d-1
,右子節點的 HD 為d+1
。
從頂部俯視這棵樹,對於每個水平距離,只能看到最淺層(深度最小)的節點。
📥 輸入格式:
第一行一個整數 n
(1 ≤ n ≤ 10⁵),表示「完全先序遍歷序列」的長度(包含 "null"
的節點)。
第二行 n
個字串,以空格分隔,為該樹的完全先序遍歷:
- 節點名稱為英文字母構成(長度 ≤ 10)。
- 空節點以字串
"null"
表示。
完全先序遍歷表示整棵樹的結構,包括不存在的空子節點。
📤 輸出格式:
一行,輸出從左到右能被看到的節點名稱,以空格分隔。
📘 輸入範例:
13
A B D null null null C null E F null null null
📗 輸出範例:
D B A C E
🔍 範例說明:
根據完全先序遍歷,可還原出二叉樹如下:
A
/ \
B C
/ \
D E
/
F
對應的水平距離:
- D:-2
- B:-1
- A:0
- C:1
- E:2
- F:1(但深度比 C 深,不會被看到)
因此,頂視圖中可見節點為:D(-2)、B(-1)、A(0)、C(1)、E(2)
🔢 資料範圍與保證:
- 每個非空節點的名稱唯一,且只出現一次。
n
≤ 10⁵。- 節點總數(非 null 的節點數)≤ 10⁵。
- 保證輸入序列能構成一棵合法的二叉樹。
Related
In following homework: