剑指Offer 34.二叉树中和为某一值的路径 dfs+回溯

题目

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

叶子节点 是指没有子节点的节点。

示例 1：

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

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

示例 3：

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

提示：

• 树中节点总数在范围 [0, 5000] 内
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

dfs+回溯算法，图中右边的线都是回溯的操作。每次到新节点都会在队列尾部添加元素，继续向左、右节点遍历到底，如果当前节点是上一个节点的左节点，回溯上一个节点之后继续遍历右节点，再进行回溯。

题解

class Solution {
    
    List<List<Integer>> lists = new LinkedList<List<Integer>>();
    Deque<Integer> path = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
    
        dfs(root,target);
        return lists;
    }
    public void dfs(TreeNode root ,int target){
    
        if (root == null){
    
            return;
        }
        path.offerLast(root.val);
        target -= root.val;
        if (root.left == null && root.right == null && target == 0){
    
            lists.add(new LinkedList<Integer>(path));
        }
        dfs(root.left,target);
        dfs(root.right,target);
        path.pollLast();//回溯
    }
}