【アルゴリズムとデータ構造の関連】【LeetCode】【437経路総和III】【Python】

テーマ:二叉木が与えられ、その各ノードには整数値が格納されています.パスと指定した値に等しいパスの合計数を見つけます.パスはルートノードから開始する必要もなく、リーフノードで終了する必要もありませんが、パスの方向は下向きでなければなりません(親ノードから子ノードまでのみ).ツリーは1000ノードを超えず、ノードの数値範囲は[-10000001000000]の整数です.
例:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

   3。    8     :

1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11

考え方:第一感覚はダイナミックプランニングで行うべきであり,二つのケース(1)ルートノードがターゲットパスにある場合,左右のサブツリーに対してsum=sum-rootをそれぞれ探す.valのパスでいいです.(2)ルートノードがターゲットパスにない場合,左右のサブツリーに対してsum=sumのパスをそれぞれ探し,美しく見えるかどうか!簡単だよね!しかし、問題があります.sum=sum-rootを再帰的に探しています.valのパスの場合、見つかったパスが不連続になります.例で示したツリーのように、10->-2というパスが見つかります(信じないなら自分で試してみてください!)、だから1つの比較的愚かな方法しか採用できません:遍歴のような方法で、各ノードから合法的な経路があるかどうかを下に探します
コード:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        if not root:
            return 0
        count = 0
        queue = [root]
        while len(queue) > 0:
            x = queue.pop(0)
            count += self.rootSum(x, sum)
            if x.right:
                queue.append(x.right)
            if x.left:
                queue.append(x.left)
        return count
    def rootSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        count = 0
        if not root:
            return count
        if root.val == sum:
            count+=1
        count += self.rootSum(root.left, sum - root.val)
        count += self.rootSum(root.right, sum - root.val)
        return count

これはもちろん可能ですが、効率が低すぎて、大量の繰り返し計算が存在するため、ノードごとにsum_を維持することを改善します.lstは、現在のノードがあるターゲットパスの終点である可能性のある値セットと、兄弟ノードのペアごとの値セットが同じである場合、はっきり言えません.具体的にはコードを見てください.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        if not root:
            return 0
        sum_lst = [sum]
        return self.pathSum_1(root, sum_lst)
    def pathSum_1(self, root, sum_lst):
        count = 0
        sum = sum_lst[-1]
        if not root:
            return count
        count += sum_lst.count(root.val)
        sum_lst = [x-root.val for x in sum_lst]
        sum_lst.append(sum)
        count += self.pathSum_1(root.left, sum_lst)
        count += self.pathSum_1(root.right, sum_lst)
        return count