php实现二叉树中和为某一值的路径方法

 更新时间£º2018年10月14日 14:50:08   投稿£ºlaozhang   我要评论

在本篇文章中我们给大家分享了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;

}

以上就是本?#25991;?#23481;的全部实例代码£¬大家可以本次测试一下£¬感谢大家对脚本之家的支持¡£

相关文章

  • php把字符串指定字符分割成数组的方法

    php把字符串指定字符分割成数组的方法

    下面小编就为大家分享一篇php把字符串指定字符分割成数组的方法£¬具有很好的参考价值£¬希望对大家有所帮助¡£一起跟随小编过来看看吧
    2018-03-03
  • thinkPHP框架整合tcpdf插件操作示例

    thinkPHP框架整合tcpdf插件操作示例

    这篇文章主要介绍了thinkPHP框架整合tcpdf插件操作,结合实例形式较为详细的分析了thinkPHP框架整合tcpdf插件的具体步骤¡¢相关操作技巧与注意事项,需要的朋友可以参考下
    2018-08-08
  • php自定义session示例分享

    php自定义session示例分享

    这篇文章主要介绍了php自定义session示例,需要的朋友可以参考下
    2014-04-04
  • php二维数组按某个键值排序的实例讲解

    php二维数组按某个键值排序的实例讲解

    今天小编就为大家分享一篇关于php二维数组按某个键值排序的实例讲解£¬小编觉得内容挺不错的£¬现在分享给大家£¬具有很好的参考价值£¬需要的朋友一起跟随小编来看看吧
    2019-02-02
  • CodeIgniter多语言实现方法详解

    CodeIgniter多语言实现方法详解

    这篇文章主要介绍了CodeIgniter多语言实现方法,结合实例形式较为详细的分析了CodeIgniter实现多语言的具体步骤¡¢实现方法与相关注意事项,需要的朋友可以参考下
    2016-01-01
  • Yii2 输出xml格式数据的方法

    Yii2 输出xml格式数据的方法

    这篇文章主要介绍了Yii2 输出xml格式数据的方法的相关资料,小编感觉非常具有参考价值£¬特此分享到脚本之家平台£¬供大家参考
    2016-05-05
  • Symfony2实现从数据库获取数据的方法小结

    Symfony2实现从数据库获取数据的方法小结

    这篇文章主要介绍了Symfony2实现从数据库获取数据的方法,结合实例形式总结分析了常用的Symfony数据库查询技巧,需要的朋友可以参考下
    2016-03-03
  • php版微信公众平台之微信网页登陆授权示例

    php版微信公众平台之微信网页登陆授权示例

    这篇文章主要介绍了php版微信公众平台之微信网页登陆授权的方法,结合实例形式分析了微信网页登陆授权的接口调用及参数含义,需要的朋友可以参考下
    2016-09-09
  • 分享5个非常有用的Laravel Blade指令

    分享5个非常有用的Laravel Blade指令

    这篇文章主要给大家分享介绍了5个非常有用的Laravel Blade指令£¬文中通过示例代码介绍的非常详细£¬对大家的学习或者工作具有一定的参考学习价值£¬需要的朋友们下面随?#21028;?#32534;来一起学?#25226;?#20064;吧
    2018-05-05
  • thinkPHP分组后模板无法加载问题解决方法

    thinkPHP分组后模板无法加载问题解决方法

    这篇文章主要介绍了thinkPHP分组后模板无法加载问题解决方法,分析了thinkPHP分组后模板无法加载的原因与相应的设置方法,需要的朋友可以参考下
    2016-07-07

最新评论

ÁÉÄþ35Ñ¡7¿ª½±½á¹û