路径总和II

问题简述

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

叶子节点 是指没有子节点的节点。

113. 路径总和 II - 力扣（LeetCode）

思路

• 先序遍历+回溯；

Python

# 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: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        
        ret = []
        tmp = []

        def dfs(x, rest):
            if not x:
                return 
            
            rest -= x.val
            tmp.append(x.val)
            if not x.left and not x.right:
                if rest == 0:
                    ret.append(tmp[:])
                
            dfs(x.left, rest)
            dfs(x.right, rest)
            rest += x.val
            tmp.pop()
        
        dfs(root, targetSum)
        return ret