113路径总和II

佚名 4年前 (2020-06-16) Python 547人围观抢沙发百度已收录

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