leetCode ✏Leetcode基础刷题之(113. Path Sum II)
✏描述
给定一个二叉树和一个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);
}
}
转载链接：https://leetcode.cn/
![[爱了]](/js/img/d1.gif)
![[尴尬]](/js/img/d16.gif)