在本篇文章中我们给大家分享了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
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);
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; $<a style="color:transparent">来源gao($daima.com搞@代@#码网</a>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实现二叉树中和为某一值的路径方法的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：php实现二叉树中和为某一值的路径方法
转载请注明原文链接：php实现二叉树中和为某一值的路径方法
