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


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

0b1f32495cb18883dde3395d5612c0a2.png

题目描述

给定一个二叉树和一个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);
    }
}

吴亲库里 has written 98 articles

情绪只是对自己无能的愤怒

积分:4787 等级:P8 职业:php 城市:杭州

0 条回复

登录后才能进行评论,立即登录?