|
| 1 | +# 113. 路径总和 II |
| 2 | + |
| 3 | +[url](https://leetcode-cn.com/problems/path-sum-ii/) |
| 4 | + |
| 5 | + |
| 6 | +## 题目 |
| 7 | + |
| 8 | +给你二叉树的根节点 `root` 和一个整数目标和 `targetSum` ，找出所有 **从根节点到叶子节点** 路径总和等于给定目标和的路径。 |
| 9 | + |
| 10 | +**叶子节点** 是指没有子节点的节点。 |
| 11 | + |
| 12 | + |
| 13 | + |
| 14 | +``` |
| 15 | +输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 |
| 16 | +输出：[[5,4,11,2],[5,8,4,5]] |
| 17 | +``` |
| 18 | + |
| 19 | +## 方法 |
| 20 | + |
| 21 | +可递归，当然也可迭代 |
| 22 | + |
| 23 | +## code |
| 24 | + |
| 25 | +### js |
| 26 | + |
| 27 | +```js |
| 28 | +let pathSum = (root, sum) => { |
| 29 | + let ret = [] |
| 30 | + let dfs = (node, sum, list) => { |
| 31 | + if (node === null) |
| 32 | + return; |
| 33 | + list.push(node.val); |
| 34 | + sum -= node.val; |
| 35 | + if (sum === 0 && node.left === null && node.right === null) { |
| 36 | + ret.push(list.slice()) |
| 37 | + } else { |
| 38 | + dfs(node.left, sum, list); |
| 39 | + dfs(node.right, sum, list); |
| 40 | + } |
| 41 | + list.pop(); |
| 42 | + } |
| 43 | + dfs(root, sum, []); |
| 44 | + return ret; |
| 45 | +} |
| 46 | +``` |
| 47 | + |
| 48 | +### go |
| 49 | + |
| 50 | +```go |
| 51 | +func pathSum(root *TreeNode, targetSum int) [][]int { |
| 52 | + var ret [][]int |
| 53 | + var dfs func(node *TreeNode, sum int, list []int) |
| 54 | + dfs = func(node *TreeNode, sum int, list []int) { |
| 55 | + if node == nil { |
| 56 | + return |
| 57 | + } |
| 58 | + list = append(list, node.Val) |
| 59 | + sum -= node.Val |
| 60 | + if sum == 0 && node.Left == nil && node.Right == nil { |
| 61 | + ret = append(ret, append([]int{}, list...)) |
| 62 | + } else { |
| 63 | + dfs(node.Left, sum, list) |
| 64 | + dfs(node.Right, sum, list) |
| 65 | + } |
| 66 | + list = list[:len(list)-1] |
| 67 | + } |
| 68 | + dfs(root, targetSum, []int{}) |
| 69 | + return ret |
| 70 | +} |
| 71 | +``` |
| 72 | + |
| 73 | +### java |
| 74 | + |
| 75 | +```java |
| 76 | +class Solution { |
| 77 | + private List<List<Integer>> ret = new ArrayList<>(); |
| 78 | + public List<List<Integer>> pathSum(TreeNode root, int sum) { |
| 79 | + |
| 80 | + dfs(root, sum, new ArrayList<Integer>()); |
| 81 | + return ret; |
| 82 | + } |
| 83 | + |
| 84 | + private void dfs(TreeNode node, int sum, ArrayList<Integer> list) { |
| 85 | + if (node == null) |
| 86 | + return; |
| 87 | + list.add(node.val); |
| 88 | + sum -= node.val; |
| 89 | + if (sum == 0 && node.left == null && node.right == null) |
| 90 | + ret.add(new ArrayList(list)); |
| 91 | + else { |
| 92 | + dfs(node.left, sum, list); |
| 93 | + dfs(node.right, sum, list); |
| 94 | + } |
| 95 | + list.remove(list.size() - 1); |
| 96 | + } |
| 97 | +} |
| 98 | +``` |
| 99 | + |
0 commit comments