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);  //往前回溯一個狀态
	  }
           

同樣的也可以不用輔助函數，寫在一個函數裡，但是那樣要把結果集合程式設計全局變量