劍指offer：二叉樹中和為某一值的路徑

題目描述
輸入一顆二叉樹的跟節點和一個整數，打印出二叉樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。(注意: 在返回值的list中，數組長度大的數組靠前)

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    # 返回二維列表，內部每個列表表示找到的路徑
    """
    根據題目定義，一個路徑總是從根節點開始的，而搜索路徑本質上又和樹的遍歷有關，那么我們可以思考常
    用的樹的遍歷中哪種遍歷方法可能有效，在這里答案就是先序遍歷，因為先序遍歷也是從根節點開始的。
    由于題目要求搜索所有可能的路徑，一個路徑在一層里面只經過一個節點，那么就是深度優先搜索DFS。

    具體到路徑的定義，需要從根節點到葉節點，因此每遍歷到一個節點的時候，如果這個節點是葉節點，那么
    我們就應該判斷當前的路徑是否符合要求，而如果這個節點不是葉節點，那么就選擇一個子節點繼續遍歷。
    當一個節點的所有子節點都已經訪問完畢之后，由于遞歸的特性會自動返回到其父節點，因此我們需要手動
    從路徑中刪除這個節點
    """
    def FindPath(self, root, expectNumber):
        def helper(cur_root, path):
            # 遍歷到一個節點的時候先將其加入路徑中
            path.append(cur_root.val)
            # 如果這個節點是葉節點，那么判斷當前路徑是否符合要求
            if not cur_root.left and not cur_root.right:
                if sum(path) == expectNumber:
                    # 這里注意不能res.append(path)，因為path只是一個id，綁定了內存中的
                    # 一個列表，而我們后面還會修改這個列表，因此需要將當前路徑的一個拷貝加到
                    # 返回結果當中
                    res.append(path[:])

            # 如果當前節點不是葉節點，那么訪問其子節點
            if cur_root.left:
                helper(cur_root.left, path)
            if cur_root.right:
                helper(cur_root.right, path)

            # 在訪問完這個節點的所有子節點之后會返回到其父節點中，
            # 在返回之前應該在路徑中刪除這個節點
            path.pop(-1)

        if not root:
            return []

        res = []
        helper(root, [])
        return res

def main():
    root = TreeNode(10)
    root.left = TreeNode(5)
    root.right = TreeNode(12)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(7)

    solution = Solution()
    print(solution.FindPath(root, 22))

if __name__ == '__main__':
    main()