摘要：只要我們能夠有一個以某一中間路徑和為的哈希表，就可以隨時判斷某一節(jié)點能否和之前路徑相加成為目標值。

最新更新請見：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

要求是否存在一個累加為目標和的路徑，我們可以把目標和減去每個路徑上節(jié)點的值，來進行遞歸。

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

基本的深度優(yōu)先搜索，思路和上題一樣用目標和減去路徑上節(jié)點的值，不過要記錄下搜索時的路徑，把這個臨時路徑代入到遞歸里。

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

給定一個二叉樹，其中可能有正值也可能有負值。求可能有多少種自上而下的路徑（但不一定要是從根節(jié)點到葉子節(jié)點），使得路徑上數(shù)字之和等于給定的數(shù)字。

這里題目有點不清楚的地方在于，雖然明確提到路徑必須是從父節(jié)點到子節(jié)點自上而下，但實際上在OJ評判時，單個節(jié)點也可以算是一個路徑。

既然路徑可以是從任意父節(jié)點自上向下到任意子節(jié)點，那么最直接的做法就是對每個節(jié)點自身都做一次深度優(yōu)先搜索，看以該節(jié)點為根能找到多少條路徑。該解法在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)
實際上由于在遍歷二叉樹時，已經(jīng)得到了之前路徑上節(jié)點的信息，我們可以將路徑存下來避免再次遍歷同一個節(jié)點。這樣根據(jù)記錄下的路徑，只需要計算以當前節(jié)點為底端，向上的路徑中符合要求的解即可。這個解法避免了大量遞歸，所以在OJ上并不會超時。

from collections import deque

class Solution:
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        path = deque() #把新節(jié)點放在前面
        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: #從當前節(jié)點沿著路徑向上加，因為新節(jié)點都放在了頭，所以不用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

然而，記錄路徑還是需要遍歷一遍這個路徑，如何省去這次遍歷呢？由于我們不需要知道路徑的順序信息，只需要知道存在過多少段段路徑，它的和加上當前節(jié)點就是目標值。那么是否可以用哈希表來記錄這個多少段路徑呢？不過問題在于，哈希表的value是路徑的數(shù)量，但是不知道如何確定哈希表的key。

這里有個非常巧妙的辦法，類似于two sum的思路，就是當你想知道A+B=C何時會成立，我們可以通過將B哈希表內(nèi)，如果C-A的值在這個哈希表中出現(xiàn)，即說明存在這么一個組合，使得A+B=C。而本題中，我們想知道的何時“當前節(jié)點值”+“某一中間路徑和”=“目標值” （把鄰接當前節(jié)點但不一定包含根節(jié)點的路徑叫做中間路徑）。只要我們能夠有一個以“某一中間路徑和”為key的哈希表，就可以隨時判斷某一節(jié)點能否和之前路徑相加成為目標值。

但是“某一路徑和”如何計算呢？我們在遍歷的時候，只有從根到當前節(jié)點的路徑和。“當前節(jié)點累加的根路徑和” = “之前某一節(jié)點中累加的根路徑和” + “某一中間路徑和” + “當前節(jié)點值” （把從根開始算的路徑叫做根路徑），所以“某一中間路徑和” = “當前節(jié)點累加的根路徑和” - “之前某一節(jié)點中累加的根路徑和” - “當前節(jié)點值”，代入上一個公式，我們可得“當前節(jié)點累加的根路徑和” - “之前某一節(jié)點中累加的根路徑和” = “目標值”

由于“當前節(jié)點累加的根路徑和”和“目標值”我們都知道，所以意味著只要將“之前某一節(jié)點中累加的根路徑和”作為哈希表的key存儲，我們就能當場判斷是否存在這一組合使得等式成立。

class Solution:
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        prevSums = { 0: 1 } # 之前某一節(jié)點中累加的根路徑和所構成的字典，初始時只有一個根路徑和為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) # 當前根路徑和 - 目標值 = 之前某一節(jié)點中累加的根路徑和，看有多少種滿足此等式的情況
        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