#LEETCODE113. 路徑總和 II(Path Sum II)

路徑總和 II(Path Sum II)

題目名稱:總和路徑(Path Sum II)

題目描述:

給定一棵二叉樹及一個整數 S,請找出所有從根節點葉子節點的路徑,使得該路徑上所有節點的數值加總為 S

每一條符合條件的路徑請以節點值的序列方式輸出,並按照字典序升序排列


輸入格式:

第一行為一個整數 n(0 ≤ n ≤ 5000),表示層序遍歷序列中的節點個數(含 null 占位符)。 第二行為 n 個字串(以空格分隔),為層序遍歷結果,空節點使用 null 表示,其餘為整數。 第三行為一個整數 S,表示目標總和。


輸出格式:

  • 若存在一條或多條總和為 S 的根到葉子路徑,請每行輸出一條路徑,節點值之間以空格分隔。
  • 所有路徑請依字典序(lexicographical order)升序輸出
  • 若沒有任何符合條件的路徑,輸出 0 行。

輸入範例 1:

13
5 4 8 11 null 13 4 7 2 null null 5 1
22

輸出範例 1:

img

5 4 11 2
5 8 4 5

輸入範例 2:

img

3
1 2 3
5

輸出範例 2:

(無輸出)


說明:

  • 層序遍歷中,null 表示該節點為空,用於補齊完整二叉樹的結構。
  • 所有節點值為整數,並可能包含負數。
  • 所有合法路徑皆應輸出,且需依照路徑的整體字典序從小到大排序。

資料範圍與限制:

  • 0 ≤ n ≤ 5000
  • −1000 ≤ 節點值 ≤ 1000(不含 null
  • −1000 ≤ S ≤ 1000