题目

• 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
• 叶子节点 是指没有子节点的节点。

示例

• 示例1

picture

输入：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

picture

输入：root = [1,2,3], targetSum = 5
输出：[]

代码

• 解法：回溯 题解 from

class Solution {
    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>(); 
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        recur(root, sum);
        return res;
    }
    void recur(TreeNode root, int tar) {
        if(root == null) return;
        path.add(root.val);
        tar -= root.val;
        if(tar == 0 && root.left == null && root.right == null)
            // 这里要新开辟空间，防止后面path的改动影响到之前添加的元素
            res.add(new LinkedList(path));  
        recur(root.left, tar);
        recur(root.right, tar);
        path.removeLast();
    }
}

代码分析：
1、本题有很多不好理解的地方，需要多看几遍。题中要求找的路径为从根节点到叶子节点,所以没必要剪枝了。
2、其次要注意的是，本题叶子结点的定义为没有子节点的节点，就有了这一句

if(tar == 0 && root.left == null && root.right == null)
    res.add(new LinkedList(path));  

3、上句代码中res.add(new LinkedList(path))，这里一定是要新开辟空间的，因为回溯的时候path的值会有所调整，新开辟空间为了防止影响到之前已经被添加的元素。

4、这三句代码的顺序不能变，因为我们一定要等一个结点的左右子部分全部讨论完，才能向上回退 (回溯)

recur(root.left, tar);
recur(root.right, tar);
path.removeLast();

• C++：AcWing

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> findPath(TreeNode* root, int sum) {
        cur(root,sum);
        return res;
    }
    void cur(TreeNode* root, int sum){
        if(!root)    return;
        sum -= root->val;
        path.push_back(root->val);
        if(!sum && !root->left && !root->right)   res.push_back(path);
        cur(root->left,sum);
        cur(root->right,sum);
        path.pop_back();
    }
};

代码分析：2、这次我用 C++ 又做了一次，一起放在这吧。这次做的时候，疏忽了一个地方。
2、刚开始这里我在 path.push_back(root->val); 前面加了if(sum >= 0) ，我想：小于 0 就直接剪枝提高效率，后来发现不能这样，详解如下：

      5
     / \
    4   6
   /   / \
  12  13  6
 /  \    / \
9    1  5   1

到 9 时 sum 为负了，如果 9 不添加进去，回溯时 pop() 出来的就是 12，相当于 12 没有添加进去

题目：二叉树中和为某一值的路径