#LAISIR17. 最深層節點總和

最深層節點總和

🧮 題目名稱:最深層節點總和

📝 題目描述:

給定一棵二元樹的完全先序遍歷(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

📗 輸出範例:

15

🧠 說明:

這棵樹結構為:

        1
      /   \
     2     3
    / \     \
   4   5     6

最深層為第 3 層(根為第 1 層),節點值為 4, 5, 6,總和為 4 + 5 + 6 = 15


📊 數據範圍:

  • 1 ≤ n ≤ 10^5
  • 非空節點總數 ≤ 10^5
  • 所有非空節點值互不相同
  • 輸入保證是合法的完全先序遍歷,能還原出一棵唯一的二元樹