113. Path Sum II

🟠   🔖  树 深度优先搜索 回溯 二叉树  🔗 LeetCode

题目

Given the root of a binary tree and an integer targetSum, return _all root-to-leaf paths where the sum of the node values in the path equals _ targetSum . Each path should be returned as a list of the node values , not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22

Output: [[5,4,11,2],[5,8,4,5]]

Explanation: There are two paths whose sum equals targetSum:

5 + 4 + 11 + 2 = 22

5 + 8 + 4 + 5 = 22

Example 2:

Input: root = [1,2,3], targetSum = 5

Output: []

Example 3:

Input: root = [1,2], targetSum = 0

Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 5000].
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

题目大意

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。说明: 叶子节点是指没有子节点的节点。

解题思路

思路一：DFS

这道题可以使用深度优先搜索（DFS）进行解答。具体思路如下：

1. 使用 DFS 遍历二叉树的所有路径，同时记录当前路径和。
2. 在遍历的过程中，维护一个路径列表，记录当前路径上的所有节点。
3. 当遍历到叶子节点时，判断当前路径和是否等于目标和，如果等于则将当前路径加入结果列表。
4. 最终返回结果列表。

思路二：递归

这一题是 第 112 题 和 第 257 题 的组合增强版。

第 112 题 要求判断树中是否存在从根节点到叶子节点路径总和等于给定目标和； 第 257 题 要求返回所有从根节点到叶子节点的路径；而本题要求返回所有从根节点到叶子节点路径总和等于给定目标和的路径。可以结合两道题的解题思路，采用递归实现。

代码

DFS

/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number[][]}
 */
var pathSum = function (root, targetSum) {
	let res = [];
	let path = [];
	const dfs = (node, sum) => {
		if (!node) return;

		// 将当前节点添加到路径中
		path.push(node.val);
		sum += node.val;

		// 如果当前节点为叶子节点且路径和等于目标和，将路径加入结果列表
		if (!node.left && !node.right && sum == targetSum) {
			res.push([...path]);
		}

		// 递归遍历左右子树
		dfs(node.left, sum);
		dfs(node.right, sum);

		// 回溯，移除当前节点
		path.pop();
	};

	// 调用内部的深度优先搜索函数
	dfs(root, 0);
	return res;
};

递归

/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number[][]}
 */
var pathSum = function (root, targetSum) {
	let res = [];
	if (!root) return res;
	if (!root.left && !root.right && root.val == targetSum) {
		return [[root.val]];
	}
	let tempLeft = pathSum(root.left, targetSum - root.val);
	if (tempLeft.length) {
		for (let i of tempLeft) {
			res.push([root.val, ...i]);
		}
	}
	let tempRight = pathSum(root.right, targetSum - root.val);
	if (tempRight.length) {
		for (let i of tempRight) {
			res.push([root.val, ...i]);
		}
	}
	return res;
};

相关题目

相关题目

• 112. 路径总和
• 257. 二叉树的所有路径
• 437. 路径总和 III
• 🔒 Path Sum IV
• 2096. 从二叉树一个节点到另一个节点每一步的方向

- [112. 路径总和](./0112.md)
- [257. 二叉树的所有路径](./0257.md)
- [437. 路径总和 III](https://leetcode.com/problems/path-sum-iii)
- [🔒 Path Sum IV](https://leetcode.com/problems/path-sum-iv)
- [2096. 从二叉树一个节点到另一个节点每一步的方向](https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another)