113. 路径总和 II-Toy模板网

这篇具有很好参考价值的文章主要介绍了113. 路径总和 II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

原题链接：

113. 路径总和 II
https://leetcode.cn/problems/path-sum-ii/

完成情况：

113. 路径总和 II,# LeetCode题解,深度优先,算法,leetcode 文章来源地址https://www.toymoban.com/news/detail-573148.html

解题思路：

	/**解题思路：
	
	 *  和之前一样，dfs
	 *  然后用一个List去记录每次走的路径，
	 *  最后用给一个List.remove删除掉走过的痕迹
	 *
	 */

参考代码：

package 西湖算法题解___中等题;

import java.util.ArrayList;
import java.util.List;

public class __113路径总和II__输出路径上的所有元素 {
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode() {}
		TreeNode(int val) { this.val = val; }
		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}


	List<List<Integer>> res = new ArrayList<List<Integer>>();
	List<Integer> everyTry = new ArrayList<>();
	public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
		/**解题思路：
		 *  和之前一样，dfs
		 *  然后用一个List去记录每次走的路径，
		 *  最后用给一个List.remove删除掉走过的痕迹
		 *
		 */
		dfs(root,0,targetSum);
		return res;
	}

	/**
	 *
	 * @param root
	 * @param num
	 * @param targetSum
	 */
	private void dfs(TreeNode root, int num, int targetSum) {
		if (root == null){
			return;
		}
		num += root.val;
		everyTry.add(root.val);
		if (num == targetSum && root.left == null && root.right == null){   //满足这个条件，说明走到底了
			res.add(new ArrayList<>(everyTry));
		}
		dfs(root.left,num,targetSum);
		dfs(root.right,num,targetSum);
		everyTry.remove(everyTry.size()-1);
	}
}