主題

LeetCode - 437. Path Sum III 解題心得

Not In My Back Yard | 2021-05-02 00:00:08 | 巴幣 0 | 人氣 25

題目連結:


題目意譯:
給定一棵二元樹的根節點 root 以及一整樹 targetSum,回傳路徑總數其路徑上的數值總和等於 targetSum。

路徑不一定需要開始於根節點、結束於葉節點,但是它必須是方向向下的(即只從父母節點往子節點的方向探訪下去)。

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



範例測資:
範例 1:
輸入: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
輸出: 3
解釋: 和為 8 的路徑如上圖所示。

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


解題思維:
類似於前面的系列題(這題這題),也是以深度優先搜尋(Depth First Search)找出每條從根節點到葉節點的路徑,然後在過程中維護該路徑經過的數字以及路徑總和。

我們可以將其中一條路徑視為一個獨立的數列。而我們用一個雜湊表 H (Hash Table)來儲存這個數列各個前綴和(Prefix Sum)之值(即遞迴時會得到的當前路徑和)。

當我們位於遞迴中的第 i 層時,我們有著當前的路徑和 S 以及一個雜湊表 H。此時我們去 H 中找是否存在 S - target 之值。

如果有則代表我們找到了一段路徑(形成路徑和 S - target 的路徑結尾 ~ 當前路徑之結尾),而這樣子的路徑有 H[S - target] 個。

找完 S - target 完之後,將 H[S] 加 1 以示路徑和 S 的個數多了一條(現在這條)。然後繼續遞迴下去搜尋。當搜尋完回來到第 i 層時,此時我們應將 H[S] 減去 1,否則其他分支的路徑可能會使用到本條路徑的路徑和。

而所求即是搜尋中所有 H[S - target] (如果存在)之和。




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

創作回應

更多創作