7.15 第一次做，无法 AC
7.16 不能一次 AC
7.17 差一点点 AC
7.18 一次 AC

题目描述

原题链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/

解题思路：回溯法：先序遍历+路径记录

K 神题解：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/solution/

• 特别的：

  • K 神并没有正面直接去计算路径和然后与 target 进行比较；
  • 而是变相的用 target 减去每一个路过的节点值，当 target 为0的时候，若此时到达的是叶子节点（root.left == null && root.right ==null），则就侧面表明此时的路径和就是为 targret ！如果到达叶子节点了，但是 target 的值还没减到0，则路径和就肯定不是 target 了！

• 心得：做二叉树遍历题时，要懂得抓住遍历到叶子节点时的特性与所求题目进行结合，不一定要正面解决问题，可以从侧面解决！

7.16 心得：

• 这是处理业务的递归回溯，不是判断对错的递归回溯！
• 处理业务：所以终止条件就只需要写本题持续不了的情况，也就是当前节点为 null，就没办法继续了。

• 然后再结合因为是二叉树的先序遍历，所以接下来就是“对当前节点干什么”的环节！

• 这题因为返回值比较复杂，所以最后把要返回的变量定义为全局的，然后在原方法进行返回，并且再写一个递归函数去遍历二叉树，将得到的结果加到全局变量的结果集里面就行了，这样就简单很多了，也不用耦合在一个方法里面，重新写的递归函数甚至返回值直接写成 void 就行了，因为不用你返回啥！

  class Solution {
    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        recur(root,target);
        return res;
    }
    public void recur(TreeNode root, int target) {
        if(root == null) return;
        path.add(root.val);
        target -= root.val;
        if(target == 0 && root.left == null && root.right == null) {
            // 这里传进去的 path 必须重新 new 一个，相当于保存一个快照
            // 如果不重新 new 一个，显而易见的，因为 path 对象只有最开始定义的那一个
            // 最后 res 结果集保存的就都是一样的 path 了！而且最致命的是，都为空！
            res.add(new LinkedList(path));
        }
        recur(root.left, target);
        recur(root.right, target);
        path.removeLast();
    }
  }