【算法与数据结构相关】【LeetCode】【437 路径总和 III】【Python】

题目：给定一个二叉树，它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

示例：

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这个路径（不信可以自己试一下！），所以只能采用一种比较笨的方法：用类似于遍历的方法，从每一个节点出发向下寻找是否存在合法路径

代码：

# 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