Title Source: https://leetcode-cn.com/problems/path-sum-ii/description/

Title Description:

Algorithm description:

1. This is the upgraded version of the previous blog. See for details. https://blog.csdn.net/qq_39241239/article/details/82749696 

2. The difficulty of comparing this question with the previous one is to output each path. So we should use backtracking algorithm.

3. First, a result set list is needed to store all the final paths. You also need an intermediate set, arrlist, to hold a path.

4. When traversing a node, first add the value of the node to the intermediate set. If the current node has no children and the path to the node meets the requirements, the intermediate set will be added to the result set. If the node has a left subtree, it traverses the left subtree. If the node has a right subtree, then it traverses the right subtree.

5. It should be noted that when traversing a path (whether it meets the requirements or not) to return to the place of function call, the last element of the middle set should be deleted (this reflects the backtracking).

The code is as follows:

class Solution {
	public List<List<Integer>> pathSum(TreeNode root, int sum) {
		//Define a result set
		List<List<Integer>> list = new ArrayList<>();
		if (root == null) {
			return list;
		}
		//Define an intermediate set
		ArrayList<Integer> arrlist = new ArrayList<>();
		path(root, list, arrlist, sum);
		return list;
	}

	public void path(TreeNode root, List<List<Integer>> list, ArrayList<Integer> arrlist, int nowSum) {
		//Add the value of the current node to the intermediate set
		arrlist.add(root.val);
		nowSum -= root.val;
		if (root.left == null && root.right == null) {
			if (nowSum == 0) {
				//If the current node has no children, judge whether the path meets the requirements. If it does, add the path to the result set
				list.add(new ArrayList<Integer>(arrlist));
			}
			//After traversing a path, you will return to the call point. You can also return without writing return. But adding return can slightly improve efficiency.
			return;
		}
		if (root.left != null) {
			//If the left subtree is not empty, recursively traverse the left subtree. Note that after the function returns, the last element of the middle set should be deleted (the backtracking is reflected here)
			path(root.left, list, arrlist, nowSum);
			arrlist.remove(arrlist.size() - 1);
		}
		if (root.right != null) {
			//If the right subtree is not empty, recursively traverse the right subtree. Note that after the function returns, the last element of the middle set should be deleted (the backtracking is reflected here)
			path(root.right, list, arrlist, nowSum);
			arrlist.remove(arrlist.size() - 1);
		}
	}
}