php实现二叉树中和为某一值的路径方法
发布:smiling 来源: PHP粉丝网 添加日期:2021-10-31 20:01:25 浏览: 评论:0
二叉树中和为某一值的路径:
输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径,路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径,(注意: 在返回值的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;
- }
Tags: php二叉树 php某一值路径
相关文章
- ·php 二叉树遍历算法与例子(2015-04-08)
- ·PHP完全二叉树定义与实现方法示例(2021-08-11)
推荐文章
热门文章
最新评论文章
- 写给考虑创业的年轻程序员(10)
- PHP新手上路(一)(7)
- 惹恼程序员的十件事(5)
- PHP邮件发送例子,已测试成功(5)
- 致初学者:PHP比ASP优秀的七个理由(4)
- PHP会被淘汰吗?(4)
- PHP新手上路(四)(4)
- 如何去学习PHP?(2)
- 简单入门级php分页代码(2)
- php中邮箱email 电话等格式的验证(2)