Leetcode基础刷题之PHP解析(113. Path Sum II)

上一题链接Leetcode基础刷题之PHP解析(216. Combination Sum III)

题目描述

给定一个二叉树和一个num值，找出这棵树所有从根节点到叶子节点等于num值的全部组合。 

题目分析

/**
 * 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[][]
     */
    function pathSum($root, $sum) {
        if(!$root) return [];
        $res=[];
        $out=[];
        $this->helper($root,$sum,$res,$out);
        return $res;
    }
    
    function helper($root,$sum,&$res,$out)
    {
        if(!$root) return ;
        array_push($out,$root->val);
        if($sum==$root->val && !$root->left && !$root->right){
            array_push($res,$out);
        }
        $this->helper($root->left,$sum-$root->val,$res,$out);
        $this->helper($root->right,$sum-$root->val,$res,$out);
        array_shift($out);
    }
}

Github整理地址:https://github.com/wuqinqiang/leetcode-php