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;



}



以上就是本次内容的全部实例代码，大家可以本次测试一下，感谢大家对中文源码网的支持。