🟡 剑指 Offer 34. 二叉树中和为某一值的路径

LeetCode 提示

题目难度 中等

原题链接 🔗 leetcode

题解 1.py

# 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 = rightclass Solution:    def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:        res = []        def dfs(node, cur, newTarget):            if not node:                return            if not node.left and not node.right and node.val == newTarget:                res.append(cur+[node.val])                return            if node.left:                dfs(node.left, cur+[node.val], newTarget-node.val)            if node.right:                dfs(node.right, cur+[node.val], newTarget-node.val)                dfs(root, [], target)        return res

题解 2_节省空间.py

# 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 = rightclass Solution:    def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:        res = []        stacks = []        def dfs(node, newTarget):            if not node:                return            if not node.left and not node.right and node.val == newTarget:                res.append(stacks+[node.val])                return            if node.left:                stacks.append(node.val)                dfs(node.left, newTarget-node.val)                stacks.pop(-1)            if node.right:                stacks.append(node.val)                dfs(node.right, newTarget-node.val)                stacks.pop(-1)                dfs(root, target)        return res