当前位置：首页 > news >正文

【Leetcode】剑指Offer 34：二叉树中和为某一值的路径

news 来源：原创 2024/5/8 0:18:24

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
叶子节点是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：[]
示例 3：
输入：root = [1,2], targetSum = 0
输出：[]
提示：
树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

AC代码

# 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, target: int) -> List[List[int]]:
        res = []
        def dfs(node:TreeNode, temp:List):
            if node.left == None and node.right == None:
                current = 0
                for i in temp:
                    current += i.val
                if current == target:
                    res.append([i.val for i in temp])
            else:
                if node.left != None:
                    temp.append(node.left)
                    dfs(node.left, temp)
                    temp.remove(node.left)
                if node.right != None:
                    temp.append(node.right)
                    dfs(node.right, temp)
                    temp.remove(node.right)
        
        if root == None:
            return []
        dfs(root, [root])
        return res

此题人肉debug了两遍才发现最开始写错的地方，主要是叶子节点部分，其实在上一步就已经添加了，最后只需要直接求和就可以进行比较。

官方题解

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        res, path = [], []
        def recur(root, tar):
            if not root: return
            path.append(root.val)
            tar -= root.val
            if tar == 0 and not root.left and not root.right:
                res.append(list(path))
            recur(root.left, tar)
            recur(root.right, tar)
            path.pop()

        recur(root, sum)
        return res

作者：jyd
链接：https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/solution/mian-shi-ti-34-er-cha-shu-zhong-he-wei-mou-yi-zh-5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。