LeetCode Easy/Medium 112/113パスの和1/2 Python

112
方法1:
アルゴリズムアルゴリズム:シーケンスループ
考え方:
ツリーを巡り、パスの和を記録し、現在のノードがリーフノードである場合、前のパスの和+リーフノードを
の値をsumと比較する、等しければself.find=True、遡及するために現在のパスのpath_を変更しないsum
値は,左右に遍歴したときに,本ノードvalを加えた値を下に伝える.
ここでinitにグローバル変数findを設定して、再帰中の結果を関数に戻すことを保証します.
boolは可変データ型なので、リストとは異なり、関数で変更すると直接結果を持ち出します.
find=True、関数はfind=Trueに新しいローカル変数を作成し、このローカル変数の値をTrueに等しくするので仕方ありません
持って行って、globalで持って行くと言っていますが、私は試してみましたが、持って行かなかったので、とても愚かで、関数のためかもしれません.
再帰的に持って行かなかったでしょう
後の完全再帰バージョンは、再帰で結果をどのように返すか、どのようにreturnするかをよりよく理解します.
複雑度分析:
時間:ON、ノード毎に1回のみアクセス
空間:ON、すべてのノードを巡回し、スタック空間を再帰する

def hasPathSum(self, root, sum):

    def pre_travel(root, path_sum):

        if root == None:

            return

        else:

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

                if path_sum + root.val == sum:

                    self.find = True

            pre_travel(root.left, path_sum + root.val)

            pre_travel(root.right, path_sum + root.val)

    pre_travel(root, 0)

    return self.find

方法2:
完全再帰バージョンv 1
最初に直さなかったのは、returnが自信がなかったからだ.if root==Noneのところのreturnだけなら
実はここのreturnは葉ノードの再帰を終了するだけで、上層は、再帰呼び出しの場所を返します.
    self.hasPathSum(root.left,sum-root.val)-->次の層returnはself.find
    self.次の層はselfをreturnしたfind
そして関数実行が終了し,つまり左右を巡回した後に左右を巡回した結果を返さなかったため,出力はNoneである.
だから最後にreturnすべきで、ここでreturnの両者のorもreturn self.findでもいいし、どうせ
最後に戻ったのはselfです.findはTrueとしてのみ使用できます

def hasPathSum2(self, root, sum):

    if root == None:

        return self.find

    else:

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

            if sum - root.val == 0:

                self.find = True

    return self.hasPathSum(root.left,sum-root.val ) or self.hasPathSum(root.right,sum-root.val)

方法3:
完全再帰バージョンv 2
    ....
だから最後にreturnすべきで、ここでreturnの両者のorもreturn self.findでもいいし、どうせ
最後に戻ったのはselfです.findはTrueとしてのみ使用できます

def hasPathSum3(self, root, sum):

    if root == None:

        return self.find

    else:

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

            if sum - root.val == 0:

                self.find = True

        self.hasPathSum(root.left, sum - root.val)

        self.hasPathSum(root.right, sum - root.val)

    return self.find

113
アルゴリズムアルゴリズム:再帰先順ループ
考え方:
112に似ていますが、ここではsumのパスとして記録します.
同様に伝参の時にpath+[root.val]で下に伝わってこの層が遡及する時pathが変わっていないことを保障します
このようにプラス記号+パスは、現在のレイヤのpath値に影響を与えない新しい変数を下に転送します.
複雑度分析:
時間:ON、すべてのノードを巡回する
空間:ON、すべてのノードに必要な再帰スタックの空間とresultの空間を遍歴する

def pathSum( root, sum):

    def pre_travel(root, path_sum, path):

        if root == None:

            return

        else:

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

                if path_sum + root.val == sum:

                    result.append(path + [root.val])

            pre_travel(root.left, path_sum + root.val, path + [root.val])

            pre_travel(root.right, path_sum + root.val, path + [root.val])

    result = []

    pre_travel(root, 0, [])

    return result