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

 ?phphtml' target='_blank'>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-  $list[]=$root-  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-  $list[]=$root-  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如何实现二叉树中和为某一值的路径（代码）的详细内容，PHP教程

郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。