leetcode hot100

437. 路径总和 III

已解答

中等

相关标签

相关企业

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

简单算法是遍历一遍所有节点，然后去搜索这个节点开始的所有路径的总和是不是符合条件

# Definition for a binary tree node.

# class TreeNode(object):

#     def __init__(self, val=0, left=None, right=None):

#         self.val = val

#         self.left = left

#         self.right = right

class Solution(object):

    def pathSum(self, root, targetSum):

        """

        :type root: Optional[TreeNode]

        :type targetSum: int

        :rtype: int

        """

        self.ret = 0

        if root:

            queue = [root]

        else:

            queue=[]

        def dfs(tmp,targetSum):

            if tmp==None:

                return 0

            else:

                if tmp.val == targetSum:

                    self.ret+=1

                dfs(tmp.left,targetSum-tmp.val)

                dfs(tmp.right,targetSum-tmp.val)

        while len(queue):

            tmp = queue[0]

            x1 = dfs(tmp,targetSum)

            del queue[0]

            if tmp.left:

                queue.append(tmp.left)

            if tmp.right:

                queue.append(tmp.right)

        return self.ret

难的办法没看懂