大家好，我是河海哥，专注于后端，如果可以的话，想做一名code designer而不是普通的coder，一起见证河海哥的成长，您的评论与赞是我的最大动力，如有错误还请不吝赐教，万分感谢。一起支持原创吧！纯手打有笔误还望谅解。
1-1：description
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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum-ii
1-2: recursion
??路径之和II 相比路径之和I 的区别在于，路径之和II 需要将路径进行输出，并且用的是list，那么用list我们就知道需要回溯，并且回溯的时候就要进行退出操作，因为上一个的节点不能留着当作下一个路径上的节点，比如 1 2 3，2是左，3是右，当遍历完2的时候转向右节点去遍历的时候，list中是[1, 2] ，如果不退出一个2，再加入3就是[1, 2, 3]了，自然不行。当然这里面对于java来说还有一个问题，我们先看代码：
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<Integer> path = new ArrayList<>();
List<List<Integer>> result = new ArrayList<>();
traverse(root, targetSum, path, result);
return result;
}
public void traverse(TreeNode root, int targetSum, List<Integer> path, List<List<Integer>> result) {
if (root == null) {
return;
}
path.add(root.val);
if (root.left == null && root.right == null) {
if (targetSum == root.val) {
result.add(new ArrayList<>(path));
// result.add(path);
}
}
traverse(root.left, targetSum - root.val, path, result);
if (root.left != null) {
path.remove(path.size() - 1);
}
traverse(root.right, targetSum - root.val, path, result);
if (root.right != null) {
path.remove(path.size() - 1);
}
}
最坏时间复杂度：O（N^2）
空间复杂度：O(H)，栈的递归深度就是树的高度
??仔细分析下代码，我们主要是两个部分，一个回退部分，我感觉这样写 会比较好理解，左边遍历完回退一次，右边遍历完也回退一次。然后遇见满足条件的节点，将路径加入到结果list中，没有任何问题，但是，请仔细观察注释掉的这段代码，这两者一样吗？有区别的，当我们找到找到目标的时候，将path加入到result，然后回溯的时候，不得弹出吗？比如 1 2 3，我们找到了1 2 path=[1 , 2]，result = [[1, 2]]，回溯path = [1] result中呢？result = [path]，对不对，path在java中是引用，所以result里面的path也会被改变，变成 result = [1]，所以，我们一定要加入一个new ArrayList，这样就不会出现这种情况了。
1-3：iteration
??迭代法应该也挺好写的，主要优化点就在于可以用一个hashmap去记录住节点之间的父子关系，这样就等于记住了整个路径了，然后再用两个queue 一边记录节点，一遍记录从根到该节点的总和值，一边遍历一边判别应该就好了。
