LeetCode

Appearance

113. Path Sum II ​

题目 ​

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

 

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: []

Example 3:

Input: root = [1,2], targetSum = 0
Output: []

 

Constraints:

  • The number of nodes in the tree is in the range [0, 5000].
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000
Related Topics
  • 树
  • 深度优先搜索
  • 回溯
  • 二叉树

  • 👍 1191
  • 👎 0

    • 思路 ​

    递归三要素

    • 确定递归函数的参数和返回值
      • 本题递归函数需要传入 节点、当前target、当前path
      • 本题不止一个返回值，故返回值记录在全局变量中，无需递归函数返回值处理
    • 终止条件
      • 本题求 root 到 leaf 之间的距离和，终止条件为当前节点为 叶子节点
      • not root.left and not root.right
    • 递归逻辑
      • 本题记录了 path 需要进行 path 回溯的撤销

    解法 ​

    py
    # leetcode submit region begin(Prohibit modification and deletion)
# 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]]:
        self.res = []
        if not root:
            return self.res

        def dfs(root, target, path):

            path.append(root.val)

            if not root.left and not root.right:
                if target == root.val:
                    self.res.append(path[:])
                path.pop()
                return

            if root.left:
                dfs(root.left, target - root.val, path)

            if root.right:
                dfs(root.right, target - root.val, path)

            path.pop()


        dfs(root, targetSum, [])

        return self.res

        
# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    • 时间复杂度 O(N)
    • 空间复杂度 O()