#LAISIR18. 二元樹左視圖
二元樹左視圖
🧮 題目名稱:二元樹左視圖
📝 題目描述:
給定一棵二元樹的**完全先序遍歷(Preorder Traversal)**序列,請你還原這棵樹,並輸出從左側觀看這棵樹時能看到的節點值(即每層最左側的節點)。
先序遍歷中,空節點以 "null"
表示。
📥 輸入格式:
-
第一行一個整數
n
(1 ≤ n ≤ 10^5
),表示先序序列的長度(包括"null"
)。 -
第二行包含
n
個字串,以空格分隔,為完全先序遍歷序列:- 節點為
-10^5
到10^5
間的整數 - 空節點為字串
"null"
- 節點為
📤 輸出格式:
- 多行,每行一個整數,按層從上至下輸出每層最左側節點值。
📘 輸入範例:
13
1 2 4 null null 5 null null 3 null 6 null null
📗 輸出範例:
1
2
4
🧠 說明:
這棵樹結構為:
1
/ \
2 3
/ \ \
4 5 6
每層最左邊的節點為:
- 第 1 層:
1
- 第 2 層:
2
- 第 3 層:
4
因此答案為 1\n2\n4
📊 數據範圍:
1 ≤ n ≤ 10^5
- 非空節點總數 ≤
10^5
- 所有非空節點值互不相同
- 輸入保證為合法的完全先序遍歷,可還原唯一合法二元樹
Related
In following homework: