题目地址(113. 路径总和 II)

https://leetcode-cn.com/problems/path-sum-ii/

题目描述

  1. 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
  3. 叶子节点 是指没有子节点的节点。
  7. 示例 1：
  9. 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
  10. 输出：[[5,4,11,2],[5,8,4,5]]
  13. 示例 2：
  15. 输入：root = [1,2,3], targetSum = 5
  16. 输出：[]
  19. 示例 3：
  21. 输入：root = [1,2], targetSum = 0
  22. 输出：[]
  27. 提示：
  29. 树中节点总数在范围 [0, 5000] 内
  30. -1000 <= Node.val <= 1000
  31. -1000 <= targetSum <= 1000

前置知识


公司

  • 暂无

思路

关键点


代码

  • 语言支持：Java

Java Code:

  2. /**
  3.  * Definition for a binary tree node.
  4.  * public class TreeNode {
  5.  *     int val;
  6.  *     TreeNode left;
  7.  *     TreeNode right;
  8.  *     TreeNode() {}
  9.  *     TreeNode(int val) { this.val = val; }
  10.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  11.  *         this.val = val;
  12.  *         this.left = left;
  13.  *         this.right = right;
  14.  *     }
  15.  * }
  16.  */
  17.     class Solution {
  18.         public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
  19.             //返回值
  20.             List<List<Integer>> res = new ArrayList<>();
  21.             //节点判空
  22.             if (root == null) {
  23.                 return res;
  24.             }
  25.             //节点路径
  26.             List<Integer> path = new LinkedList<>();
  27.             loop(root, targetSum, res, path);
  28.             return res;
  29.         }
  31.         public void loop(TreeNode root,
  32.                                   int targetSum,
  33.                                   List<List<Integer>> res,
  34.                                   List<Integer> path) {
  35.             //进入递归循环就将root节点的值添加到路径中
  36.             path.add(root.val);
  37.             //递归到了叶子节点 判断给定值减去当前的节点值是否=0 如果=就将整个路径加到res中 然后返回 如果不等于就直接返回
  38.             if (root.left == null && root.right == null) {
  39.                 if (targetSum - root.val == 0) {
  40.                     //注意这里不要直接加path 
  41.                     res.add(new ArrayList<>(path));
  42.                 }
  43.                 return;
  44.             }
  45.             //递归调用左节点
  46.             if (root.left != null) {
  47.                 loop(root.left, targetSum-root.val , res, path);
  48.                 //回溯 调用完左节点后执行 目的是将递归过的节点的值从路径中移除
  49.                 path.remove(path.size() - 1);
  50.             }
  51.             //递归调用左节点
  52.             if (root.right != null) {
  53.                 loop(root.right, targetSum-root.val , res, path);
  54.                 path.remove(path.size() - 1);
  55.             }
  56.         }
  57.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：113. 路径总和 II - 图1#card=math&code=O%28n%29&id=wXRrT)
  • 空间复杂度：113. 路径总和 II - 图2#card=math&code=O%28n%29&id=jSgrw)