こんにちは
今回の学びは
・合計の差分を持ち歩くというのと、葉の判定がポイントの問題です
問題はpath-sum
（時間配分は5分問題理解=restate&clarify 10分検討multip-sol, analysis, reasons 10分実装 20分振り返り の一文45分構成)をできればgoogle docで笑&真剣。
終始、わからないことは声にだして、明確にしていきましょう。
１，まずは入出力をしっかりおさえましょう。（問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと）
２，いくつかのソリューションを声にだして出してみましょう。（もちろんtime complexit, space complexityの分析や理由を付け加えて）
３，どれでいくか、一緒に決定しましょう。（理由付きでね、よろしく）
timespace analysis (時間とスペースの分析）は 〇〇です
場合によっては、pseudocode（擬似コード）をかいてみてもよい。
４、実装しましょう。
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def __str__(self):
return "val:%s, left:%s, right:%s" % (self.val,
self.left.val if self.left else "none",
self.right.val if self.right else "none",
)
def bt_sum(node, k, path):
paths = []
if node:
rest = k - node.val
path_copy = path[:]
path_copy.append(node.val)
is_leaf = node.left is None and node.right is None
if is_leaf:
if rest == 0:
return [path_copy]
else:
return []
else:
paths += bt_sum(node.left, rest, path_copy)
paths += bt_sum(node.right, rest, path_copy)
return paths
root = TreeNode(10)
root.left = TreeNode(16)
root.right = TreeNode(5)
root.left.right = TreeNode(-3)
root.right.left = TreeNode(6)
root.right.right = TreeNode(11)
path = []
ans = bt_sum(root, 26, path)
print(ans)
よくする間違い！
配列(path)を引数として持たす時、参照として持ち歩くので、その影響がわかっていない
赤字でコピーするのがポイント。いっつも、ハマるので注意。このために配列をコピーして走査するのでstackの積み重ねO(logN) * O(N)のspaceが必要で非常にメモリ効率はよくない
def bt_sum(node, k, path):
paths = []
if node:
rest = k - node.val
path_copy = path[:]
path_copy.append(node.val)
is_leaf = node.left is None and node.right is None
if is_leaf:
if rest == 0:
return [path_copy]
else:
return []
else:
paths += bt_sum(node.left, rest, path_copy)
paths += bt_sum(node.right, rest, path_copy)
return paths
ちなみに、メモリ効率はテスト結果としては悪くないです。下の関数は返却値が{true|false}ですが、上の関数ではpathのリストを全て返すようにしています。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
"""
edge case: (initial acc is 0 , what if sum = 0 is given?!)
root = [1], sum = 0
edge case: ( return True only if it reaches to the end of branch)
https://leetcode.com/submissions/detail/289318789/
root = [1, 2], sum = 1
"""
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
def bt_sum(node, k, path):
paths = []
if node:
rest = k - node.val
path_copy = path[:]
path_copy.append(node.val)
is_leaf = node.left is None and node.right is None
if is_leaf:
if rest == 0:
return [path_copy]
else:
return []
else:
paths += bt_sum(node.left, rest, path_copy)
paths += bt_sum(node.right, rest, path_copy)
return paths
return len(bt_sum(root, sum, [])) > 0
def hasPathSum2(self, root: TreeNode, sum: int) -> bool:
# dfsでaccumulative sumをcarry on すればよい
def dfs_accumulate(node, goal: int, acc:int,) -> bool:
if node is None: return False
_acc = 0 if acc == None else acc
_acc_new = _acc + node.val
is_leaf = (node.left == None and node.right == None)
if _acc_new == goal and is_leaf:
return True
if node.left:
if dfs_accumulate(node.left, goal, _acc_new): return True
if node.right:
if dfs_accumulate(node.right, goal, _acc_new): return True
return False
if root is None: return False
return dfs_accumulate(root, sum, None)
５、エッジケースとサンプルテストを忘れずに！
合計の差分を持ち歩くというのと、葉の判定がポイントの問題です
振り返り
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
まとめ
以上です