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

Created 5 years ago by 吴亲库里, Updated 5 years ago Revision #1 2304 views 0 likes 0 collects

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

题目描述

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

题目分析

第一想到的就是深度优先搜索啊，从根节点出发，一条路走到黑,是的话保存结果，继续换一条路。我们需要两个临时变量，一个变量用来返回最终结果，另一个变量用来保存每次dfs存储的路径值，还需要注意的是，每次dfs的搜索的时候，一定发现子节点不是我们要查找的值，那么久应该把push进去的值重新踢出来，最终的实现是递归。

/**
 * 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);
    }
}