Skip to content

Latest commit

 

History

History
65 lines (53 loc) · 2.04 KB

113.md

File metadata and controls

65 lines (53 loc) · 2.04 KB

✏️Leetcode基础刷题之(113. Path Sum II)

2019-08-06 吴亲库里 库里的深夜食堂

✏️描述

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

联系

​