113. 路径总和 II

题意：

解题思路：

思路：O(n2)（这题跟112基本一样，不同点在于把所有符合条件的路径记录下来）
1. 递归，从根节点出发，每经过一个叶节点，用sum减去该叶节点值，直到走到叶节点；
2. 如果走到叶节点，sum差值为0，则说明找到了从根节点到叶节点的数之和等于sum值；
3. 递归返回即可；

PHP代码实现：

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    /**
     * @param TreeNode $root
     * @param Integer $sum
     * @return Integer[][]
     */
    public $res = [];
    function pathSum($root, $sum) {
        if ($root == null) return $this->res;
        $this->helper($root, [], $sum);
        return $this->res;
    }
    function helper($root, $array, $sum) {
        if ($root == null) return;
        array_push($array, $root->val);
        if ($root->left == null && $root->right == null) {
            if ($sum - $root->val == 0) {
                array_push($this->res, $array);
            }
            return;
        }
        $this->helper($root->left, $array, $sum - $root->val);
        $this->helper($root->right, $array, $sum - $root->val);
    }
}

GO代码实现：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var res [][]int
func pathSum(root *TreeNode, sum int) [][]int {
    res = [][]int{}
    helper(root, []int{}, sum)
    return res
}
func helper(root *TreeNode, array []int, sum int) {
    if root == nil {
        return
    }
    array = append(array, root.Val)
    if root.Left == nil && root.Right == nil {
        if sum == root.Val {
            r := make([]int, len(array))
            copy(r, array)
            res = append(res, r)
        }
    }
    helper(root.Left, array, sum - root.Val)
    helper(root.Right, array, sum - root.Val)
}