题目描述补充

题目：二叉树的路径和 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

class TreeNode {
    public $val;
    public $left;
    public $right;

    function __construct($val = 0, $left = null, $right = null) {
        $this->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 示例代码

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 示例代码

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);

码小课网站中有更多相关内容分享给大家学习，包括但不限于二叉树的其他遍历方式、搜索算法、动态规划等，欢迎大家访问学习。