[数据结构与算法]回溯问题-例二叉树中和为某一值的路径

一、题目

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

二、回溯问题

这道题的思路就在于二叉树的深度优先遍历，也就是先序遍历。在到达某一结点的时候，将target = target - root.val，然后再继续递归结点的左子树和右子树，看是否满足和为target。

关键点是：使用的List集合，在递归到左子树完成后，会保存左子树下结点的值（执行了path.add()操作），那么在递归右子树的时候，如果不做任何操作，path的尾部会保存当前结点左子树的数据，这一定会导致遍历右子树的时候出错。要使得在遍历右子树之前恢复到当前结点的状态，就要进行一个关键操作：回溯。具体做法就是，在递归操作返回的时候，将path链表中最后一个结点删除，恢复到递归前的状态。

这样，就做到了在递归结束后，path链表恢复到递归前的状态，从而可以正确地进行右子树的递归。

class Solution {
    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        dfs(root,target);
        return res;
    }
    public void dfs(TreeNode root,int target){
        if(root == null){
            return;
        }
        //到达当前结点
        target = target - root.val;
        path.add(root.val);
        if(root.left == null && root.right == null && target == 0){
            res.add(new LinkedList(path));
        }
        dfs(root.left,target);
        dfs(root.right,target);
        //此时，递归调用处于当前结点。
        //上边将当前结点加入到path中，这里将这个结点删除
        //于是就将path恢复到递归到当前结点前的状态
        path.removeLast();
    }
}

思路来自于：https://blog.csdn.net/zjxxyz123/article/details/79699575