#LAISIR18. 二元樹左視圖

二元樹左視圖

🧮 題目名稱:二元樹左視圖

📝 題目描述:

給定一棵二元樹的**完全先序遍歷(Preorder Traversal)**序列,請你還原這棵樹,並輸出從左側觀看這棵樹時能看到的節點值(即每層最左側的節點)。

先序遍歷中,空節點以 "null" 表示。


📥 輸入格式:

  • 第一行一個整數 n1 ≤ n ≤ 10^5),表示先序序列的長度(包括 "null")。

  • 第二行包含 n 個字串,以空格分隔,為完全先序遍歷序列:

    • 節點為 -10^510^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
  • 所有非空節點值互不相同
  • 輸入保證為合法的完全先序遍歷,可還原唯一合法二元樹