#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⁵。
  • 保證輸入序列能構成一棵合法的二叉樹。