[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