[leet112] PathSum. 関数の変数は関数にのみ影響します

関数内の変数の変化は関数にのみ影響します

global, local variables. 当たり前のことですが、関数を再帰的に実現する過程で悩む部分もあります.この問題は簡単なDFSで解決できるので,コードに悩み点を簡単にメモする.

Question

値がroot-to-leafの和のtargetSum値に等しい場合(つまり、すべてのleafを加えた場合にtargetSumを作成できる場合)、True、そうでない場合False

Solution

DFSを普段使っている時とは違います.次のコードのansのようにpathなどのターゲットデータはhelperの外で定義され、helperは変数を非ローカルにインポートして更新することでループします.
しかし、ここではpathの和でなければならないので、pathが終わったら前に戻らなければなりません.コードと一緒に見ると、#チェックポイント!!ぶぶんtemp sumがパラメータとして受信されず、非局所更新で更新されると、for loopの前の演算は非局所temp sumを変更するので、この時点の値に戻るのは難しい.
上記の例示的な図を簡単に例に挙げると、11−>7まで計算された後、11−>2に戻り、temp sum値は7に加算された.7万を引いてもいいことではありません.右の8->4->1の場合、さらに8->13へ行くと4と1を外します...
しかし、このコードが実行されると、dfs helper(7,20)が次の要素にコマンドを返すdfs helper(2,temp sum)では、temp sumも20で動作する.27ではありません.
どうしたんですか.dfs helper(7,20)ではtemp sumが変化したが,関数外部のtemp sumは変化しなかった.長い間悩んでいましたが、基本的には当たり前です.やっぱり基礎はしっかりして….

def hasPathSum(root, targetSum):
    if not root: return False
    ans = False

    def dfs_helper(root, temp_sum):
        nonlocal ans, targetSum
        temp_sum += root.val
        if not root.left and not root.right:
            if temp_sum == targetSum:
                ans = True
            return
        
        togo = [node for node in [root.left, root.right] if node]
        for node in togo:
            #cur_sum = temp_sum
            dfs_helper(node, temp_sum) # checkpoint!!!
    dfs_helper(root, 0)
    return ans