113. 路径总和 II 深度优先搜索 + 回溯法

113. 路径总和 II

难度：中等

相似题目：路径总和1

题目描述

解题思路

还是用深度优先搜索来实现，因为深度优先搜索的特点是每一步之间差别很小，所以很适合用来完成回溯问题

这道题和1的区别是要记录满足目标的路径，只需要修改一些细节就可以了

/*
	   * 113. 路径总和 II
	   * 2020/5/14  要求记录路径
	   * 回溯法  设置现场 递归 恢复现场
	   */
	  public List<List<Integer>> pathSum(TreeNode root, int sum) {
		  List<List<Integer>> re = new LinkedList<List<Integer>>();
		  if(root == null)
			  return re;
		  List<Integer> temp = new LinkedList<Integer>();
		  pathHelper(re,temp,root,sum);
		  return re;
	    }
	  public void pathHelper(List<List<Integer>> re,List<Integer> temp,TreeNode root, int sum) {
		  if(root == null)
			  return;
		  sum -= root.val;
		  temp.add(root.val);
		  if(root.left == null && root.right == null) {//如果到了叶子节点
			  if(sum == 0) 
				  re.add(new LinkedList<Integer>(temp));
			  temp.remove(temp.size()-1);  //往前回溯一个状态
			  return;
		  }
		  pathHelper(re, temp, root.left, sum);
		  pathHelper(re, temp, root.right, sum);
		  temp.remove(temp.size()-1);  //往前回溯一个状态
	  }
           

同样的也可以不用辅助函数，写在一个函数里，但是那样要把结果集合编程全局变量