[leetcode] path sum II (first glimpse recursion + backtracking)

#LeetCode A daily topic 【 Special topic of binary tree 】

• The sum of the paths II
  https://leetcode-cn.com/problems/path-sum-ii/
• analysis
  Look for a binary tree all From the root node to the leaf node The path sum is equal to the given target sum
  Consider depth first search , Whenever a leaf node is reached , Judge whether the current value meets the goals and , To add it to the final result set ;
  It should be noted that , When a certain root node and the following nodes are traversed , Keep going up , Need to pay attention to backtracking , Otherwise, it will affect the next recursive result set
• Realization

	List<List<Integer>> ans = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    
        LinkedList<Integer> res = new LinkedList<>();
        pathSum(root, targetSum, res);
        return ans;
    }

    //  Depth-first search + to flash back 
    private void pathSum(TreeNode root, int targetSum, LinkedList<Integer> res) {
    
        if (root == null) return;
        res.add(root.val);
        if (root.left == null && root.right == null) {
    
            //  The leaf node satisfies the final condition 
            if (root.val == targetSum) {
    
                //  want new A collection goes in , Otherwise, it will be synchronously modified later 
                ans.add(new LinkedList<>(res));
            }
        }
        pathSum(root.left, targetSum - root.val, res);
        pathSum(root.right, targetSum - root.val, res);
        //  Go back , Remove the current node from the collection 
        res.pollLast();
    }

LeetCode Time consuming ：1ms

• Option two
  If you do not use backtracking , Make sure that between each recursion list Transmission does not affect each other , You can also generate a new set before each recursion , But there will be a lot of extra time and space overhead

    List<List<Integer>> ans = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    
        LinkedList<Integer> res = new LinkedList<>();
        pathSum2(root, targetSum, res);
        return ans;
    }
	//  Depth-first search + Each recursion generates a new set , Guaranteed not to interfere with other recursive branches 
    private void pathSum2(TreeNode root, int targetSum, LinkedList<Integer> res) {
    
        if (root == null) return;
        //  Every time the recursion comes in, it will re new A collection , This ensures that the parameters res Does not interfere with each other in each recursion , There is no need to go back 
        LinkedList<Integer> temp = new LinkedList<>(res);
        temp.add(root.val);
        if (root.left == null && root.right == null) {
    
            if (root.val == targetSum) {
    
                ans.add(temp);
            }
        }
        pathSum2(root.left, targetSum - root.val, temp);
        pathSum2(root.right, targetSum - root.val, temp);
    }

LeetCode Time consuming ：5ms

It can be seen that time and space have increased a lot

• summary

1. About recursion and backtracking , There are some introductions here that can deepen our understanding
   link
2. There are two ways to solve the branch pollution problem ：
   The first one is ： to flash back
   The second kind ： Each recursion creates a new object