U. 古樹守望者的視角(Top View of Binary Tree)
古樹守望者的視角(Top View of Binary Tree)
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
🧭 題目名稱:古樹守望者的視角(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⁵。
- 保證輸入序列能構成一棵合法的二叉樹。
20250522_C++_樹_練習
- Status
- Done
- Problem
- 31
- Open Since
- 2025-5-23 0:00
- Deadline
- 2025-6-27 23:59
- Extension
- 24 hour(s)