当前位置： 面试刷题>> 二叉树的路径和Ⅱ (经典算法题500道)
### 题目描述补充
**题目：二叉树的路径和 II**
给定一个二叉树，返回所有从根节点到叶子节点的路径，其中每条路径上的节点值之和都等于一个给定的目标和（targetSum）。
**注意**：
- 路径定义为从树中任意节点出发，沿父节点-子节点连接，达到任意叶子节点的序列。
- 叶子节点是指没有子节点的节点。
- 路径可以从根节点开始，且不一定经过根节点。
- 路径中的节点值（不包括目标和）的序列必须递增。
**示例**：
给定如下二叉树和目标和 `targetSum = 9`
```
5
/ \
4 8
/ / \
3 7 2
/ \
1 6
```
返回所有路径如下：
```
[
[5, 4, 0],
[5, 8, 2],
[5, 8, 2, 6],
[5, 8, 7],
[4, 3, 2],
[4, 3, 2, 6]
]
```
注意：这里的 `0` 可以被视为路径中从根节点到 `4` 节点路径上缺失的节点值（因为题目说明路径不一定经过根节点），或者你可以将其视为题目要求的一种特殊解释。实际在编码时，我们不会直接添加 `0`，而是从符合条件的子树开始构建路径。
### PHP 示例代码
```php
val = $val;
$this->left = $left;
$this->right = $right;
}
}
function pathSum($root, $targetSum) {
$result = [];
dfs($root, $targetSum, [], $result);
return $result;
}
function dfs($node, $targetSum, $path, &$result) {
if (!$node) return;
$path[] = $node->val;
if (!$node->left && !$node->right && array_sum($path) == $targetSum) {
$result[] = $path;
}
dfs($node->left, $targetSum, $path, $result);
dfs($node->right, $targetSum, $path, $result);
// 回溯，移除当前节点
array_pop($path);
}
// 示例用法
$root = new TreeNode(5);
$root->left = new TreeNode(4);
$root->right = new TreeNode(8);
$root->left->left = new TreeNode(3);
$root->left->left->left = new TreeNode(1);
$root->left->left->right = new TreeNode(6);
$root->right->left = new TreeNode(7);
$root->right->right = new TreeNode(2);
$targetSum = 9;
$result = pathSum($root, $targetSum);
print_r($result);
?>
```
### Python 示例代码
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def pathSum(root, targetSum):
result = []
def dfs(node, target, path):
if not node:
return
path.append(node.val)
if not node.left and not node.right and sum(path) == target:
result.append(path[:])
dfs(node.left, target, path)
dfs(node.right, target, path)
path.pop()
dfs(root, targetSum, [])
return result
# 示例用法
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(3)
root.left.left.left = TreeNode(1)
root.left.left.right = TreeNode(6)
root.right.left = TreeNode(7)
root.right.right = TreeNode(2)
targetSum = 9
result = pathSum(root, targetSum)
print(result)
```
### JavaScript 示例代码
```javascript
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
function pathSum(root, targetSum) {
const result = [];
function dfs(node, target, path) {
if (!node) return;
path.push(node.val);
if (!node.left && !node.right && path.reduce((a, b) => a + b, 0) === target) {
result.push([...path]);
}
dfs(node.left, target, path);
dfs(node.right, target, path);
path.pop();
}
dfs(root, targetSum, []);
return result;
}
// 示例用法
const root = new TreeNode(5);
root.left = new TreeNode(4);
root.right = new TreeNode(8);
root.left.left = new TreeNode(3);
root.left.left.left = new TreeNode(1);
root.left.left.right = new TreeNode(6);
root.right.left = new TreeNode(7);
root.right.right = new TreeNode(2);
const targetSum = 9;
const result = pathSum(root, targetSum);
console.log(result);
```
**码小课网站中有更多相关内容分享给大家学习**，包括但不限于二叉树的其他遍历方式、搜索算法、动态规划等，欢迎大家访问学习。