一、题目描述
给你二叉树的根节点 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
二、思路讲解
思路倒是很简单，就是深度优先遍历的基本思想，每次遍历的时候将节点添加进列表中，回溯时再删去，就能得到每一条路径；在遍历的同时计算路径之和，就可以判断路径和是否是目标值。
三、Java代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
//使用全局变量，避免函数里的传参，节省运行时间
List<List<Integer>> lists = new ArrayList<>();
List<Integer> list = new ArrayList<>();
int target;
public List<List<Integer>> pathSum(TreeNode root, int target) {
this.target = target;
dfs(root, 0);
return lists;
}
void dfs(TreeNode node, int sum){
if(node == null){
return;
}
list.add(node.val);
sum += node.val;
if(sum==target && node.left==null && node.right==null){
//重新开辟空间
lists.add(new ArrayList(list));
}
dfs(node.left, sum);
dfs(node.right, sum);
//回溯
list.remove(list.size()-1);
}
}
四、时空复杂度分析
时间复杂度： O(N)
空间复杂度： O(N)
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/125017.html
