前往
大廳
主題

LeetCode - 113. Path Sum II 解題心得

Not In My Back Yard | 2021-04-28 00:00:16 | 巴幣 0 | 人氣 685

題目連結:


題目意譯:
給定一棵二元樹的根節點 root 以及一個整數 targetSum,回傳所有根節點到葉節點之路徑,其路徑和等於 targetSum。

一個葉節點為沒有子節點之節點。

限制:
樹裡的節點數於範圍 [0, 5000] 中。
-1000 ≦ Node.val ≦ 1000
-1000 ≦ targetSum ≦ 1000



範例測資:
範例 1:
輸入: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
輸出: [[5,4,11,2],[5,8,4,5]]

範例 2:
輸入: root = [1,2,3], targetSum = 5
輸出: []

範例 3:
輸入: root = [1,2], targetSum = 0
輸出: []


解題思維:
這題的基礎下,紀錄目前以及先前每個深度(深度優先搜尋(Depth First Search,DSF)之遞迴深度)的節點之值。

當我們抵達葉節點時,判斷當前這條路徑(根據上面的儲存路徑資訊)之和有無等於 targetSum。如果是就將這條路徑放進答案陣列 answer 中;否則就略過此路徑。

最後搜尋完後,answer 即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作