链接 (opens new window)

class Solution {

    public $result = [];

    /**
     * @param  TreeNode  $root
     * @param  Integer  $targetSum
     * @return Integer[][]
     */
    function pathSum($root, $targetSum) {
        if ($root) {
            $this->dfs($root, $targetSum, []);
        }
        return $this->result;
    }

    function dfs($root, $targetSum, $path) {

        if (!$root || $targetSum < $root->val) {
            return;
        }

        $path[] = $root->val;
        $targetSum -= $root->val;

        //printf("root:%d,target:%d,path:%s\n", $root->val, $targetSum, implode(" ", $path));
        //如果是叶子节点且与目标值相等 那么找到了一个路径解
        if (!$root->left && !$root->right && $targetSum == 0) {
            $this->result[] = $path;
            return;
        }

        $this->dfs($root->left, $targetSum, $path);
        $this->dfs($root->right, $targetSum, $path);

        //printf("B root:%d,target:%d,path:%s\n", $root->val, $targetSum, implode(" ", $path));
        //array_pop($path); // 为什么这个不需要 而像 77 有 for 循环的 需要
    }

    function dfs2($root, $targetSum, $path) {

        if (!$root) {
            return;
        }

        $path[] = $root->val;

        //如果是叶子节点且与目标值相等 那么找到了一个路径解
        if (!$root->left && !$root->right && $targetSum == $root->val) {
            $this->result[] = $path;
            return;
        }

        //printf("root:%d,target:%d,path:%s\n", $root->val, $targetSum, implode(" ", $path));

        $this->dfs2($root->left, $targetSum - $root->val, $path);
        $this->dfs2($root->right, $targetSum - $root->val, $path);
        //array_pop($path); // 为什么这个不需要 而像 77 有 for 循环的 需要 (因为这里两个分支之间没有修改 $path 副本的值)
    }
}

copy success