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

最新更新請(qǐng)見：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.

時(shí)間 O(b^(h+1)-1) 空間 O(h) 遞歸?？臻g 對(duì)于二叉樹b=2

要求是否存在一個(gè)累加為目標(biāo)和的路徑，我們可以把目標(biāo)和減去每個(gè)路徑上節(jié)點(diǎn)的值，來(lái)進(jìn)行遞歸。

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]
]

時(shí)間 O(b^(h+1)-1) 空間 O(h) 遞歸?？臻g 對(duì)于二叉樹b=2

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

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

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

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

既然路徑可以是從任意父節(jié)點(diǎn)自上向下到任意子節(jié)點(diǎn)，那么最直接的做法就是對(duì)每個(gè)節(jié)點(diǎn)自身都做一次深度優(yōu)先搜索，看以該節(jié)點(diǎn)為根能找到多少條路徑。該解法在OJ上會(huì)超時(shí)。

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)

時(shí)間 O(N^2)
實(shí)際上由于在遍歷二叉樹時(shí)，已經(jīng)得到了之前路徑上節(jié)點(diǎn)的信息，我們可以將路徑存下來(lái)避免再次遍歷同一個(gè)節(jié)點(diǎn)。這樣根據(jù)記錄下的路徑，只需要計(jì)算以當(dāng)前節(jié)點(diǎn)為底端，向上的路徑中符合要求的解即可。這個(gè)解法避免了大量遞歸，所以在OJ上并不會(huì)超時(shí)。

from collections import deque

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

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

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

但是“某一路徑和”如何計(jì)算呢？我們?cè)诒闅v的時(shí)候，只有從根到當(dāng)前節(jié)點(diǎn)的路徑和。“當(dāng)前節(jié)點(diǎn)累加的根路徑和” = “之前某一節(jié)點(diǎn)中累加的根路徑和” + “某一中間路徑和” + “當(dāng)前節(jié)點(diǎn)值” （把從根開始算的路徑叫做根路徑），所以“某一中間路徑和” = “當(dāng)前節(jié)點(diǎn)累加的根路徑和” - “之前某一節(jié)點(diǎn)中累加的根路徑和” - “當(dāng)前節(jié)點(diǎn)值”，代入上一個(gè)公式，我們可得“當(dāng)前節(jié)點(diǎn)累加的根路徑和” - “之前某一節(jié)點(diǎn)中累加的根路徑和” = “目標(biāo)值”

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

class Solution:
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        prevSums = { 0: 1 } # 之前某一節(jié)點(diǎn)中累加的根路徑和所構(gòu)成的字典，初始時(shí)只有一個(gè)根路徑和為0
        return self.findSolution(root, prevSums, 0, sum)
    
    def findSolution(self, root, prevSums, currSum, target):
        if root is None:
            return 0
        currSum += root.val # 累加得到當(dāng)前的根路徑和
        selfCount = prevSums.get(currSum - target, 0) # 當(dāng)前根路徑和 - 目標(biāo)值 = 之前某一節(jié)點(diǎn)中累加的根路徑和，看有多少種滿足此等式的情況
        prevSums[currSum] = prevSums.get(currSum, 0) + 1 # 把當(dāng)前根路徑和也作為之前根路徑和存起來(lái)，然后開始下一層的遞歸
        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