113. 路径总和

问题113 路径总和 ★★☆☆☆

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

这个题目需要做的是遍历二叉树的每一条path，可以称为path遍历，而path遍历其实就是前序遍历，只不过我们需要在遍历过程中维护当前的path

	public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
		List<List<Integer>> result = new ArrayList<>();
		List<TreeNode> path = new ArrayList<>();

		dfs(result, path, root, targetSum);

		return result;
	}

	private void dfs(List<List<Integer>> result, List<TreeNode> path, TreeNode node, int target) {
		if (node == null) {
			return;
		}

		path.add(node);

		if (node.left == null
			&& node.right == null) {
			if (node.val == target) {
				result.add(path.stream().map(e -> e.val).toList());
			}
		}

		if (node.left != null) {
			dfs(result, path, node.left, target - node.val);
		}

		if (node.right != null) {
			dfs(result, path, node.right, target - node.val);
		}

		path.remove(path.size() - 1);
	}

完全可以抽象出path遍历的代码如下：

	private static void paths(TreeNode node, List<TreeNode> path) {
		if (node == null) {
			return;
		}

		path.add(node);

		if (node.left == null
			&& node.right == null) {
			pathVisit(path);
		}

		if (node.left != null) {
			paths(node.left, path);
		}

		if (node.right != null) {
			paths(node.right, path);
		}

		path.remove(path.size() - 1);
	}

	private static void pathVisit(List<TreeNode> path) {
		List<String> vals = path.stream()
			.map(node -> node.val)
			.map(String::valueOf)
			.toList();
		System.out.println(String.join(",", vals));
	}

在 LeetCode 查看