【LeetCode 中等題】53-路徑總和II

題目描述：給定一個二叉樹和一個目标和，找到所有從根節點到葉子節點路徑總和等于給定目标和的路徑。

說明: 葉子節點是指沒有子節點的節點。

示例:

給定如下二叉樹，以及目标和 

sum = 22

，

5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
           

傳回:

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

解法1。 回溯，傳回到上一層時，記得pop，就是把剛剛那一層append的元素去掉，類似于複原自頂向下遞歸時這一層的樣子，而非遞歸到底開始回溯的時候的樣子。

class Solution(object):
    def pathSum(self, root, expectNumber):
        # write code here
        if not root:
            return []
        res = []
        path = []
        self.FindPathHelper(root, expectNumber, path, res)
        return res
    
    def FindPathHelper(self, root, target, path, res):
        if not root:
            return
        path.append(root.val)
        if root.val == target and not root.left and not root.right:
            res.append(path[:])
        self.FindPathHelper(root.left, target-root.val, path, res)
        self.FindPathHelper(root.right, target-root.val, path, res)
        path.pop() # 這個地方一定要加，不然輸出的path會多出很多元素，也是回溯的必備           

解法2。疊代的方式，用queue這個隊列維護還未周遊過的節點，一開始隻有root和截至root之前周遊的節點val這兩者構成的元組，後來先左後右添加節點資訊，先入先出，遇到葉子節點判斷和是否等于target，是則将path放到res中。

class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        if not root: return []
        
        paths = []
        queue = []
        queue.append((root, []))
        while queue:
            tree, path = queue.pop()
            if not tree.left and not tree.right:
                if self.get_sum(path) + tree.val == sum:
                    path.append(tree.val)
                    paths.append(path)
            else:
                if tree.left:
                    p = path[:]
                    p.append(tree.val)
                    queue.insert(0, (tree.left, p))
                if tree.right:
                    p = path[:]
                    p.append(tree.val)
                    queue.insert(0, (tree.right, p))
        
        return paths
    
    def get_sum(self, nums):
        
        return sum(nums)