113路徑總和II

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)
a.left = b
a.right = c
# 這道題和上一題是同一個類型的題目，用的方法是一樣的。
# 都是用深搜的方法，
from typing import List
class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        # 定義一個列表，用來存放符合題意的路徑。
        path_list = []
        self.dfs(root,sum,0,[],path_list)
        return path_list
    # num_list用來存放當前的節點值
    def dfs(self,root,sum,num_sum,num_list,path_list):
        # 如果根節點為None直接返回空列表。
        if not root :return num_list
        num_sum += root.val
        # 將每次遍歷的節點值放進當前列表。
        num_list.append(root.val)
        # 當這個路徑和等於目標和的時候，將當前列表放入路徑列表
        if not root.left and not root.right and num_sum == sum:
            path_list.append(num_list[:])
            # 同時要將當前節點從當前了列表中刪除
            num_list.pop()
            return
        if not root.left and not root.right and num_sum != sum:
            # 註意這裡判斷的是路徑和不等於目標值的時候要做的事情。
            num_list.pop()
            return
        self.dfs(root.left,sum,num_sum,num_list,path_list)
        self.dfs(root.right,sum,num_sum,num_list,path_list)
        # 最後這裡要把當前節點的值刪除。
        num_list.pop()


A = Solution()
print(A.pathSum(a,4))