[leetcode]113_路径总和II_输出所有路径

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。
找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点

示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例 2：
输入：root = [1,2,3], targetSum = 5
输出：[]
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。
示例 3：
输入：root = [], targetSum = 0
输出：[]
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

提示：
树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

解题思路：【DFS + 回溯】或者【BFS】

参考：

[leetcode]112_路径总和_判断是否存在-CSDN博客

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

class Solution:
    def buildtree(self, levelorder = []):
        if not levelorder:
            return None
        root = TreeNode(levelorder[0])
        queue = [root]
        i = 1
        while queue and i < len(levelorder):
            node = queue.pop(0)
            if levelorder[i]:
                node.left = TreeNode(levelorder[i])
                queue.append(node.left)
            i += 1
            if i < len(levelorder) and levelorder[i]:
                node.right = TreeNode(levelorder[i])
                queue.append(node.right)
            i += 1
        return root
    def dfs(self, root, res, targetSum, tmpSum):
        if not root:
            return res
        if sum(tmpSum) == targetSum and not root.left and not root.right:
            res.append(tmpSum)
        if root.left:
            self.dfs(root.left, res, targetSum, tmpSum + [root.left.val])
        if root.right:
            self.dfs(root.right, res, targetSum, tmpSum + [root.right.val])
    def bfs(self, root, res, targetSum):
        if not root:
            return res
        queue = [(root, [root.val])]
        while queue:
            node, path = queue.pop(0)
            if not node.left and not node.right and sum(path) == targetSum:
                res.append(path)
            if node.left:
                queue.append((node.left, path + [node.left.val]))
            if node.right:
                queue.append((node.right, path + [node.right.val]))
if __name__ == '__main__':
    try:
        nums = eval(input())
        solution =Solution()
        root = solution.buildtree(nums)
        targetSum = int(input())
        res = []
        if root == None:
            print(res)
        else:
            # solution.dfs(root, res, targetSum, [root.val])
            solution.bfs(root, res, targetSum)
            print(res)
    except Exception as e:
        traceback.print_exc()

仅作为代码记录，方便自学自查自纠