这篇文章主要为大家展示了“php如何实现二叉树中和为某一值的路径”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“php如何实现二叉树中和为某一值的路径”这篇文章吧。
二叉树中和为某一值的路径：
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
思路：
1、二叉树的前序遍历，中左右顺序
2、把目标值target传进去，target-=val
3、target为0并且left和right都为null，达到叶结点
4、函数外部两个数组，list数组存一条路径，listAll数组存所有路径
计算
安全
数据库
网络和加速
企业服务
FindPath(root,target)
if root==null return listAll
list[]=root.val
target-=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<?php
class TreeNode{
var $val;
var $left = NULL;
var $right = NULL;
function __construct($val){
$this->val = $val;
}
}
function FindPath($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=new TreeNode(10);
$node5=new TreeNode(5);
$node12=new TreeNode(12);
$node4=new TreeNode(4);
$node7=new TreeNode(7);
$node10->left=$node5;
$node10->right=$node12;
$node5->left=$node4;
$node5->left=$node7;
$tree=$node10;
$res=FindPath($tree,22);
var_dump($res);<?php
/*class TreeNode{
var $val;
var $left = NULL;
var $right = NULL;
function __construct($val){
$this->val = $val;
}
}*/
function FindPath($root,$target)
{
$list=array();
$listAll=array();
$res=dfs($root,$target,$list,$listAll);
return $res;
}
function dfs($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;
}以上是“php如何实现二叉树中和为某一值的路径”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注亿速云行业资讯频道！
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
