题目:113. 路径总和 II
链接:https://leetcode-cn.com/problems/path-sum-ii
给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 说明: 叶子节点是指没有子节点的节点。 示例: 给定如下二叉树,以及目标和 sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 返回: [ [5,4,11,2], [5,8,4,5] ]
解题:
1、二叉树遍历,判断是否遇到叶子节点,与此同时,sum是否和叶子节点的值相同,是则把路径添加到结果中。
代码:
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution(object): def get_sum(self, node, sum, current): cur2 = copy.copy(current) cur2.append(node.val) sum2 = sum - node.val if not node.left and not node.right: if sum2 == 0: self.res.append(cur2) return if node.left: self.get_sum(node.left, sum2, cur2) if node.right: self.get_sum(node.right, sum2, cur2) def pathSum(self, root, sum): """ :type root: TreeNode :type sum: int :rtype: List[List[int]] """ if not root: return [] self.res = [] self.get_sum(root, sum, []) return self.res
PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。
PPS:还是得日更呀,总结一下总是好的。