LeetCode 112

質問する

Approach 1. Recursion

これは私の解決策です!

class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        if not root:					[1]
            return False
        if not root.left and not root.right:		[3]
            return targetSum == root.val
        targetSum -= root.val				[2]
        return self.hasPathSum(root.left,targetSum)\
        or self.hasPathSum(root.right, targetSum)	[4]

方法
大きな面から見ると、これは復活であり、また貴重な関数である.
再帰関数を呼び出す場合はbasecaseが必要であり、更新を続行する値が必要です.
[1]はBase caseです.
ルートがNoneの場合はFalseを返します.
[2]ルートがNoneでない場合、targetSumは現在のルートを表示します.valを削除してtargetSumを更新します.
このようにして、後で根にchildrenがなければ(最後の葉であれば)、根の頂部の値を減算してtargetsumとrootを得る.valを比較するために.
[4]関数は、ルートの左、右端でそれぞれ呼び出されます.2つの中で1つだけが本当なので、答えは本当なので、orを書きます.
関数はrootです.左と根.rightを持って[1]に戻って検査を行います.
[3][2]で説明したように、ルートの左と右がNone(最後の葉であれば)の場合、targetSumとルートの値が同じかどうかを確認します.

Approach 2. DFS

class Solution(object):
    def hasPathSum(self, root: TreeNode, tar![](https://media.vlpt.us/images/hojin11choi/post/9d4a3b7d-0a9b-4f9e-bbcc-9ae4d5075b00/Screen%20Shot%202021-03-26%20at%202.59.53%20PM.png)getSum: int) -> bool:
        if not root:						[1]
            return False
        stack = [(root, targetSum - root.val)]			[2]
        while stack:						[3]
            u = stack.pop()					[4]
            if not u[0].left and not u[0].right:		[5]
                if u[1] == 0:					[6]
                    return True
            if u[0].left:					[7]
                stack.append((u[0].left, u[1]-u[0].left.val))
            if u[0].right:					[8]
                stack.append((u[0].right, u[1]-u[0].right.val))
        return False						[9]

方法
DFS方式で他人が作ったものを分析してみました.
プリントアウト後、下図のように探索しました.
[1]ルートがNoneの場合はFalseを返します.
[2]ルートがNoneでない場合、ツリー自体もtargetSumもrootです.値を減算する値が含まれます.
TargetSumの更新
[3]stackがNoneになるまでwhile loopを回します.stackがNoneで[6]の条件が満たされずTrueを返すことができない場合は[9]を使用してFalseを返す形式とする.
[4] stack.pop()の値をuに入れます.uはTreeと更新されたTargetSumがあります.
[5]u[0]は木です.Treeの左右のノードがNoneであれば.
[6][5]の条件を満たす場合は最下位ノードであり、更新されたTargetSum、u[1]が0であるか否かと比較する.そうだ.あるいは別の場所に行って探求します.
[7]Treeの左,右ノードがいずれもNoneでない場合,あるいは[6]でreturn Falseである場合,探索を再開する.
ツリーの左側ノードがNoneでない場合、スタックに新しい左側ツリーを追加し、左側ツリーの上部ノードの値を減算するtargetSum.もしそうなら、このスタックは[3]に戻り、繰り返しブラウズします.
[8][7]と同様に木の右側ノードがNoneでない場合はブラウズする.
Tree全体でターゲットSumが0でない場合、Falseが返される.

小後記

まる1週間DFSとBFSだけを解いて実力がアップしました…!ヒントを一度も見なかった5分以内に最高の答えが出た感動感動王感動.
これからも道しるべを解いて芝生を植えるように努力します.