[Leetcode] Path Sum I & II & III 路径和1,2,3

摘要：只要我们能够有一个以某一中间路径和为的哈希表，就可以随时判断某一节点能否和之前路径相加成为目标值。

最新更新请见：https://yanjia.me/zh/2019/01/...

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example: Given the below binary tree and sum = 22,
      5
     / 
    4   8
   /   / 
  11  13  4
 /        
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

时间 O(b^(h+1)-1) 空间 O(h) 递归栈空间 对于二叉树b=2

要求是否存在一个累加为目标和的路径，我们可以把目标和减去每个路径上节点的值，来进行递归。

public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root==null) return false;
        if(root.val == sum && root.left==null && root.right==null) return true;
        return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val);
    }
}

2018/2

class Solution:
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if root is None:
            return False
        if root.val == sum and root.left is None and root.right is None:
            return True
        return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)

Given a binary tree and a sum, find all root-to-leaf paths where each path"s sum equals the given sum.
For example: Given the below binary tree and sum = 22,
      5
     / 
    4   8
   /   / 
  11  13  4
 /      / 
7    2  5   1

return
[
   [5,4,11,2],
   [5,8,4,5]
]

时间 O(b^(h+1)-1) 空间 O(h) 递归栈空间 对于二叉树b=2

基本的深度优先搜索，思路和上题一样用目标和减去路径上节点的值，不过要记录下搜索时的路径，把这个临时路径代入到递归里。

public class Solution {
    
    List> res;
    
    public List> pathSum(TreeNode root, int sum) {
        res = new LinkedList>();
        List tmp = new LinkedList();
        if(root!=null) helper(root, tmp, sum);
        return res;
    }
    
    private void helper(TreeNode root, List tmp, int sum){
        if(root.val == sum && root.left==null && root.right==null){
            tmp.add(root.val);
            List one = new LinkedList(tmp);
            res.add(one);
            tmp.remove(tmp.size()-1);
        } else {
            tmp.add(root.val);
            if(root.left!=null) helper(root.left, tmp, sum - root.val);
            if(root.right!=null) helper(root.right, tmp, sum - root.val);
            tmp.remove(tmp.size()-1);
        }
    } 
}

2018/2

class Solution:
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        paths = []
        self.findSolution(root, sum, [], paths)
        return paths
    
    def findSolution(self, root, sum, path, paths):
        if root is None:
            return
        if root.val == sum and root.left is None and root.right is None:
            solution = [val for val in path]
            paths.append([*solution, root.val])
            return
        path.append(root.val)
        self.findSolution(root.left, sum - root.val, path, paths)
        self.findSolution(root.right, sum - root.val, path, paths)
        path.pop()

You are given a binary tree in which each node contains an integer
value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it
must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range
-1,000,000 to 1,000,000.
Example:

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

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

Return 3. The paths that sum to 8 are:

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

给定一个二叉树，其中可能有正值也可能有负值。求可能有多少种自上而下的路径（但不一定要是从根节点到叶子节点），使得路径上数字之和等于给定的数字。

这里题目有点不清楚的地方在于，虽然明确提到路径必须是从父节点到子节点自上而下，但实际上在OJ评判时，单个节点也可以算是一个路径。

既然路径可以是从任意父节点自上向下到任意子节点，那么最直接的做法就是对每个节点自身都做一次深度优先搜索，看以该节点为根能找到多少条路径。该解法在OJ上会超时。

class Solution(object):
    def findPath(self, root, sum):
        if root is not None:
            selfCount = 1 if root.val == sum else 0
            leftCount = self.findPath(root.left, sum - root.val)
            rightCount = self.findPath(root.right, sum - root.val)
            return selfCount + leftCount + rightCount
        return 0

    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        if root:
            return self.findPath(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)

时间 O(N^2)
实际上由于在遍历二叉树时，已经得到了之前路径上节点的信息，我们可以将路径存下来避免再次遍历同一个节点。这样根据记录下的路径，只需要计算以当前节点为底端，向上的路径中符合要求的解即可。这个解法避免了大量递归，所以在OJ上并不会超时。

from collections import deque

class Solution:
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        path = deque() #把新节点放在前面
        return self.findSolution(root, path, sum)
    
    def findSolution(self, root, path, target):
        if root is None:
            return 0
        sum = root.val
        count = 1 if sum == target else 0
        for val in path: #从当前节点沿着路径向上加，因为新节点都放在了头，所以不用reverse了
            sum += val
            if sum == target:
                count += 1
        path.appendleft(root.val)
        leftCount = self.findSolution(root.left, path, target)
        rightCount = self.findSolution(root.right, path, target)
        path.popleft()
        return leftCount + rightCount + count

然而，记录路径还是需要遍历一遍这个路径，如何省去这次遍历呢？由于我们不需要知道路径的顺序信息，只需要知道存在过多少段段路径，它的和加上当前节点就是目标值。那么是否可以用哈希表来记录这个多少段路径呢？不过问题在于，哈希表的value是路径的数量，但是不知道如何确定哈希表的key。

这里有个非常巧妙的办法，类似于two sum的思路，就是当你想知道A+B=C何时会成立，我们可以通过将B哈希表内，如果C-A的值在这个哈希表中出现，即说明存在这么一个组合，使得A+B=C。而本题中，我们想知道的何时“当前节点值”+“某一中间路径和”=“目标值” （把邻接当前节点但不一定包含根节点的路径叫做中间路径）。只要我们能够有一个以“某一中间路径和”为key的哈希表，就可以随时判断某一节点能否和之前路径相加成为目标值。

但是“某一路径和”如何计算呢？我们在遍历的时候，只有从根到当前节点的路径和。“当前节点累加的根路径和” = “之前某一节点中累加的根路径和” + “某一中间路径和” + “当前节点值” （把从根开始算的路径叫做根路径），所以“某一中间路径和” = “当前节点累加的根路径和” - “之前某一节点中累加的根路径和” - “当前节点值”，代入上一个公式，我们可得“当前节点累加的根路径和” - “之前某一节点中累加的根路径和” = “目标值”

由于“当前节点累加的根路径和”和“目标值”我们都知道，所以意味着只要将“之前某一节点中累加的根路径和”作为哈希表的key存储，我们就能当场判断是否存在这一组合使得等式成立。

class Solution:
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        prevSums = { 0: 1 } # 之前某一节点中累加的根路径和所构成的字典，初始时只有一个根路径和为0
        return self.findSolution(root, prevSums, 0, sum)
    
    def findSolution(self, root, prevSums, currSum, target):
        if root is None:
            return 0
        currSum += root.val # 累加得到当前的根路径和
        selfCount = prevSums.get(currSum - target, 0) # 当前根路径和 - 目标值 = 之前某一节点中累加的根路径和，看有多少种满足此等式的情况
        prevSums[currSum] = prevSums.get(currSum, 0) + 1 # 把当前根路径和也作为之前根路径和存起来，然后开始下一层的递归
        leftCount = self.findSolution(root.left, prevSums, currSum, target)
        rightCount = self.findSolution(root.right, prevSums, currSum, target)
        prevSums[currSum] = prevSums.get(currSum) - 1
        return leftCount + rightCount + selfCount