php实现二叉树中和为某一值的路径方法
二叉树中和为某一值的路径：
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意:在返回值的list中，数组长度大的数组靠前)
思路：
1、二叉树的前序遍历，中左右顺序
2、把目标值target传进去，target-=val
3、target为0并且left和right都为null，达到叶结点
4、函数外部两个数组，list数组存一条路径，listAll数组存所有路径
FindPath(root,target) ifroot==nullreturnlistAll list[]=root.val target-=root.val iftarget==0&&root->left==null&&root->right==null listAll[]=list FindPath(root->left,target) FindPath(root->right,target) //如果到了这条路径的跟结点，并没有达到目标，就删掉最后的结点，退回上一个结点 array_pop(list) returnlistAll
val=$val;
}
}
functionFindPath($root,$target)
{
static$list=array();
static$listAll=array();
if($root==null){
return$listAll;
}
$target-=$root->val;
$list[]=$root->val;
if($target==0&&$root->left==null&&$root->right==null){
$listAll[]=$list;
}
FindPath($root->left,$target);
FindPath($root->right,$target);
array_pop($list);
return$listAll;
}
$node10=newTreeNode(10);
$node5=newTreeNode(5);
$node12=newTreeNode(12);
$node4=newTreeNode(4);
$node7=newTreeNode(7);
$node10->left=$node5;
$node10->right=$node12;
$node5->left=$node4;
$node5->left=$node7;
$tree=$node10;
$res=FindPath($tree,22);
var_dump($res);
val=$val;
}
}*/
functionFindPath($root,$target)
{
$list=array();
$listAll=array();
$res=dfs($root,$target,$list,$listAll);
return$res;
}
functiondfs($root,$target,&$list,&$listAll)
{
if($root==null){
return$listAll;
}
$target-=$root->val;
$list[]=$root->val;
if($target==0&&$root->left==null&&$root->right==null){
$listAll[]=$list;
}
dfs($root->left,$target,$list,$listAll);
dfs($root->right,$target,$list,$listAll);
array_pop($list);
return$listAll;
}
以上就是本次内容的全部实例代码，大家可以本次测试一下，感谢大家对毛票票的支持。