golang 解法, 执行用时: 12 ms, 内存消耗: 4.9 MB, 提交时间: 2022-08-29 11:21:44

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type pair struct {
    node *TreeNode
    left int
}

func pathSum(root *TreeNode, targetSum int) (ans [][]int) {
    if root == nil {
        return
    }

    parent := map[*TreeNode]*TreeNode{}

    getPath := func(node *TreeNode) (path []int) {
        for ; node != nil; node = parent[node] {
            path = append(path, node.Val)
        }
        for i, j := 0, len(path)-1; i < j; i++ {
            path[i], path[j] = path[j], path[i]
            j--
        }
        return
    }

    queue := []pair{{root, targetSum}}
    for len(queue) > 0 {
        p := queue[0]
        queue = queue[1:]
        node := p.node
        left := p.left - node.Val
        if node.Left == nil && node.Right == nil {
            if left == 0 {
                ans = append(ans, getPath(node))
            }
        } else {
            if node.Left != nil {
                parent[node.Left] = node
                queue = append(queue, pair{node.Left, left})
            }
            if node.Right != nil {
                parent[node.Right] = node
                queue = append(queue, pair{node.Right, left})
            }
        }
    }

    return
}

golang 解法, 执行用时: 4 ms, 内存消耗: 4.4 MB, 提交时间: 2022-08-29 11:21:21

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, targetSum int) (ans [][]int) {
    path := []int{}
    var dfs func(*TreeNode, int)
    dfs = func(node *TreeNode, left int) {
        if node == nil {
            return
        }
        left -= node.Val
        path = append(path, node.Val)
        defer func() { path = path[:len(path)-1] }()
        if node.Left == nil && node.Right == nil && left == 0 {
            ans = append(ans, append([]int(nil), path...))
            return
        }
        dfs(node.Left, left)
        dfs(node.Right, left)
    }
    dfs(root, targetSum)
    return
}

python3 解法, 执行用时: 36 ms, 内存消耗: 16.6 MB, 提交时间: 2022-08-29 11:20:44

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        ret = list()
        path = list()
        
        def dfs(root: TreeNode, targetSum: int):
            if not root:
                return
            path.append(root.val)
            targetSum -= root.val
            if not root.left and not root.right and targetSum == 0:
                ret.append(path[:])
            dfs(root.left, targetSum)
            dfs(root.right, targetSum)
            path.pop()
        
        dfs(root, targetSum)
        return ret

python3 解法, 执行用时: 48 ms, 内存消耗: 16.4 MB, 提交时间: 2022-08-29 11:20:34

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        ret = list()
        parent = collections.defaultdict(lambda: None)

        def getPath(node: TreeNode):
            tmp = list()
            while node:
                tmp.append(node.val)
                node = parent[node]
            ret.append(tmp[::-1])

        if not root:
            return ret
        
        que_node = collections.deque([root])
        que_total = collections.deque([0])

        while que_node:
            node = que_node.popleft()
            rec = que_total.popleft() + node.val

            if not node.left and not node.right:
                if rec == targetSum:
                    getPath(node)
            else:
                if node.left:
                    parent[node.left] = node
                    que_node.append(node.left)
                    que_total.append(rec)
                if node.right:
                    parent[node.right] = node
                    que_node.append(node.right)
                    que_total.append(rec)

        return ret