[LeetCode] #113. Path Sum II

-

題目

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where each path's sum equals targetSum.

A leaf is a node with no children.

直覺解

構想：

把所有 root-to-leaf paths 找出來（利用 recursion + DFS）後，一一檢查總和是否為 targetSum

python 3 實作：

from copy import deepcopy 

 

 

class Solution: 

    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]: 

        paths = [] 

        if not root: 

            return paths 

         

        paths.append([]) 

        paths = self.recursion(root, deepcopy(paths)) 

         

        ans = [] 

        for path in paths: 

            if sum(path) == targetSum: 

                ans.append(path) 

        return ans 

     

    def recursion(self, root, paths): 

        if not root: 

            return [] 

         

        for path in paths: 

            path.append(root.val) 

         

        if not root.left and not root.right: 

            return paths 

 

        paths_left = self.recursion(root.left, deepcopy(paths)) 

        paths_right = self.recursion(root.right, deepcopy(paths)) 

         

        paths = paths_left + paths_right 

        return paths

效能：

Runtime: 572 ms, faster than 6.28% of Python3 online submissions for Path Sum II.
Memory Usage: 19.5 MB, less than 11.61% of Python3 online submissions for Path Sum II.

優化構想：

邊找 root-to-leaf paths，邊檢查檢查總和是否為 targetSum。因為節點的值可能是正的或負的，所以不能在中途發現 sum > targetSum 時就 return []。

python 3 實作：

from copy import deepcopy 

 

 

class Solution: 

    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]: 

        paths = [] 

        if not root: 

            return paths 

         

        paths.append([]) 

        return self.recursion(root, deepcopy(paths), targetSum, 0) 

     

    def recursion(self, root, paths, targetSum, sum): 

        if not root: 

            return [] 

         

        for path in paths: 

            path.append(root.val) 

         

        sum += root.val 

        if not root.left and not root.right: 

            if sum == targetSum: 

                return paths 

            else: 

                return [] 

 

        paths_left = self.recursion(root.left, deepcopy(paths), targetSum, sum) 

        paths_right = self.recursion(root.right, deepcopy(paths), targetSum, sum) 

         

        paths = paths_left + paths_right 

        return paths

效能：

Runtime: 552 ms, faster than 5.98% of Python3 online submissions for Path Sum II.
Memory Usage: 19.5 MB, less than 11.37% of Python3 online submissions for Path Sum II.

參考別人的解

來源：Python DFS

參考後的優化構想

不要使用 deepcopy。把 list 的深度降低，這樣 shallow copy 就夠用了。

自己的 python 3 實作：

class Solution: 

    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]: 

        paths = [] 

        if not root: 

            return paths 

         

        self.recursion(root, [], paths, targetSum, 0) 

        return paths 

     

    def recursion(self, root, path, paths, targetSum, sum): 

        if not root: 

            return  

         

        path.append(root.val) 

        sum += root.val 

        if not root.left and not root.right and sum == targetSum: 

            paths.append(path) 

            return 

         

        if root.left: 

            self.recursion(root.left, path.copy(), paths, targetSum, sum) 

        if root.right: 

            self.recursion(root.right, path.copy(), paths, targetSum, sum) 

         

        return

效能：

Runtime: 48 ms, faster than 53.55% of Python3 online submissions for Path Sum II.
Memory Usage: 19.5 MB, less than 11.37% of Python3 online submissions for Path Sum II.

研究別人的解

來源：sample 40 ms submission

研究重點：為什麼他在呼叫 pathSumRecursive 時不需要 copy currentPath

別人的 python 3 實作（已加上研究用的 print）：

class Solution: 

    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]: 

        allPaths = [] 

        currentPath = [] 

        self.pathSumRecursive(root, targetSum, currentPath, allPaths) #forgetting something? 
 

        return allPaths 

     

    def pathSumRecursive(self, root, targetSum, currentPath, allPaths): 

        print('<--') 

        if root is None: 

            print('-->') 

            return 

        print('root:', root.val) 

       

        currentPath.append(root.val) 

        print(currentPath) 

        if root.left == None and root.right == None and targetSum == root.val: 

            allPaths.append(list(currentPath)) #2 

         

        else: 

            self.pathSumRecursive(root.left, targetSum - root.val, currentPath, allPaths) 

            self.pathSumRecursive(root.right, targetSum - root.val, currentPath, allPaths) 

 

        del currentPath[-1] 

        print('del:', currentPath) 

        print('-->')

效能（沒有加 print 的版本）：

Runtime: 36 ms, faster than 97.35% of Python3 online submissions for Path Sum II.
Memory Usage: 15.4 MB, less than 88.26% of Python3 online submissions for Path Sum II.

print 出來的東西：

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]] 

<-- 

root: 5 

[5] 

<-- 

root: 4 

[5, 4] 

<-- 

root: 11 

[5, 4, 11] 

<-- 

root: 7 

[5, 4, 11, 7] 

<-- 

--> 

<-- 

--> 

del: [5, 4, 11] 

--> 

<-- 

root: 2 

[5, 4, 11, 2] 

del: [5, 4, 11] 

--> 

del: [5, 4] 

--> 

<-- 

--> 

del: [5] 

--> 

<-- 

root: 8 

[5, 8] 

<-- 

root: 13 

[5, 8, 13] 

<-- 

--> 

<-- 

--> 

del: [5, 8] 

--> 

<-- 

root: 4 

[5, 8, 4] 

<-- 

root: 5 

[5, 8, 4, 5] 

del: [5, 8, 4] 

--> 

<-- 

root: 1 

[5, 8, 4, 1] 

<-- 

--> 

<-- 

--> 

del: [5, 8, 4] 

--> 

del: [5, 8] 

--> 

del: [5] 

--> 

del: [] 

-->

研究感想

把節點 append 進去 currentPath，跑完左右兩個分枝後，用 del currentPath[-1] 把節點刪掉，重複使用同一個 currentPath，就不需要每次都複製一個新的 currentPath 來紀錄 path 了

在 pathSumRecursive 函式中，因為一直把 targetSum 減掉 root.val，所以參數位置只要放一個 targetSum 就好；不需要像我一樣，在 recursion 函式裡放了 targetSum 和 sum 兩個參數。

參考資料

研究後優化我的程式碼

python 3 實作：

class Solution: 

    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]: 

        paths = [] 

        if not root: 

            return paths 

         

        self.recursion(root, [], paths, targetSum) 

        return paths 

     

    def recursion(self, root, path, paths, targetSum): 

        path.append(root.val) 

        targetSum -= root.val 

        if not root.left and not root.right and targetSum == 0: 

            paths.append(list(path)) 

            del path[-1] 

            return 

         

        if root.left: 

            self.recursion(root.left, path, paths, targetSum) 

        if root.right: 

            self.recursion(root.right, path, paths, targetSum) 

        del path[-1] 

         

        return

效能：

Runtime: 36 ms, faster than 97.35% of Python3 online submissions for Path Sum II.
Memory Usage: 15.1 MB, less than 95.32% of Python3 online submissions for Path Sum II.

Comments

Post a Comment

Popular posts from this blog

Alpha Camp 全端開發課程學習心得

-
我喜歡邏輯，在哲學系求學時期，我花最多時間的科目，是形式邏輯。但是我一直不明白這個我相對擅長的科目，到底能用在什麼地方。我的邏輯能力，並沒有好到足夠讓我走上學術研究的路，那麼，或許我可以試著寫程式？ 學生時期的我，自認沒有錢，但是有時間。捨不得花錢去上程式設計課程，寧願自己找資源學習。去上過一些免費的程式入門課程，c++ 和 python，對我而言不是很難，但是學完之後，我還是看不出來，要怎麼靠學到的東西解決生活中遇到的問題，漸漸地就沒有動力繼續學下去。 直到出社會，存了點錢，也漸漸體會到時間的重要，終於捨得花錢投資自己，到 Alpha Camp 上專業的課程，而不是無頭蒼蠅自己亂找一通，省下許多時間，也看到自己學的東西是真的能用的，讓我有動力繼續學下去。 我還記得學到串接 api 的時候，心裡真是太激動了。以前在學免費課程時，就隱約有種「我寫的程式，範圍只侷限在我的電腦上」的貧瘠感覺，而在知道了 api 後，發現「我寫的程式可以跟世界接上線了」，頓時覺得自己非常富有。不過，後來才知道，串別人的 api 服務通常是要付費的。 大概是受了形式邏輯的影響，我在學習程式語言時，總是試圖去辨認，哪些東西是比較基本的，基本的東西是透過什麼樣的規則組合出複雜的東西。例如，變數、array、for 迴圈和 function 是基本的東西，可以用這些基本的東西組合出 array 的 reduce 方法，像這樣： function mimicReduce(array, reducerFunction, initialValue) {     if (initialValue) {         let accumulator = initialValue         for (let i = 0; i < array.length; i++) {             accumulator = reducerFunction(accumulator, array[i])         }         return accumulator     } else {         let accumulator = array[0]         for (let i = 1; i < array.length; i
Read more

在 javascript 用 regular expression 為金額加上千位數分隔符號

-
 為了方便使用者快速判斷金額，所以想加上千位數分隔符號。例如： 3000 --> 3,000 3000000 --> 3,000,000 搜尋資料後，結論： 如果數字有小數點的話，可以用  const amount = '3000.00' amount.replace(/\B(?<!\.\d*)(?=(\d{3})+(?!\d))/g, ',') 參考資料： Javascript之數值千分位符號（Comma）的顯示 如果沒有小數點的話，可以用  const amount = '3000' amount.replace(/\B(?=(\d{3})+(?!\d))/g, ',') 參考資料： [Javascrpt]轉換數字成含千分位的文字   不過這個鬼畫符的語法我完全看不懂，查資料的時候一度不肯相信這是真正的程式碼呢⋯⋯因緣際會在讀書會中，得到 Helix 同學提示的關鍵字「 regular expression」，決定試著弄懂，「amount.replace(/\B(?=(\d{3})+(?!\d))/g, ',')」到底是什麼意思。 一、 String.prototype.replace() - MDN 範例：我不小心把 world 拼成 word，想要把句子裡所有的 word 都替換成  world。 const text = 'Hello word! Hello word!' console.log(text.replace('word', 'world')) 結果印出 Hello world! Hello word! 很不幸地，只有第一個錯字有替換，其他錯字都被放生了。如果想要替換全部的 word，就要這樣寫： const text = 'Hello word! Hello word!' console.log(text.replace( /word/ g , ' world '))
Read more

shop_platform - sqlalchemy.exc.TimeoutError

-
發生的問題 啟動伺服器後，第二十一次請求「需要查詢資料庫」的頁面時，會出現「sqlalchemy.exc.TimeoutError: QueuePool limit of size 10 overflow 10 reached, connection timed out, timeout 30.00 (Background on this error at: https://sqlalche.me/e/14/3o7r )」的錯誤訊息。如果請求是不需要查詢資料庫的（例如靜態檔案或前往登入頁面），就不會發生此錯誤。 把 size 和 overflow 設定成更小的數字，可以更快重現這個錯誤 。 感覺起來，就像查詢完資料庫以後，沒有把 connection 釋出一樣，導致「size + overflow」是多少，就只能查詢多少次資料庫。 發現瀏覽器每向伺服器請求一次「需要查詢資料庫」的頁面，在 MySQL Workbench 用 show PROCESSLIST; 指令的查詢結果就會多出一筆資料，筆數達到 size + overflow 時，若再次請求「需要查詢資料庫」的頁面，就會噴 QueuePool limit of size 10 overflow 10 reached 的錯誤。關閉伺服器時，那幾筆資料才會被刪除。 嘗試過但失敗的方法 app.run(debug=False) 自己註冊一個關閉 session 的函式 @app.teardown_appcontext # 改成 @app.teardown_request 也沒用 def teardown_db(exception): db.session.remove() # 改成 db.session.close() 也沒用 print('***** session.remove') # 這一行有印出來，所以此函式有被執行 把 FLASK_ENV=development 拿掉 ，於是 FLASK_ENV 變成預設的 production app.config["SQLALCHEMY_COMMIT_ON_TEARDOWN"] = True 終於成功的方法 第一種方法：用 Ap
Read more