【アルゴリズム脳トレ】leetcode 112 Path Sum

こんにちは

今回の学びは

・合計の差分を持ち歩くというのと、葉の判定がポイントの問題です

問題は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)

５、エッジケースとサンプルテストを忘れずに！

合計の差分を持ち歩くというのと、葉の判定がポイントの問題です