php实现二叉树中和为某一值的路径方法
作者:laozhang 时间:2023-07-04 20:29:08
二叉树中和为某一值的路径:
输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的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;
}
标签:php,二叉树
0
投稿
猜你喜欢
在select语句中使用top的一些小技巧
2009-03-12 12:21:00
Python paramiko 模块浅谈与SSH主要功能模拟解析
2023-10-01 11:06:28
PHP数组中头部和尾部添加元素的方法(array_unshift,array_push)
2023-06-06 22:45:50
mysql主从复制的实现步骤
2024-01-18 02:50:25
解决Pycharm运行时找不到文件的问题
2023-06-15 00:26:39
对Python中内置异常层次结构详解
2023-10-18 11:08:49
详解supervisor使用教程
2022-02-18 09:12:07
Python request设置HTTPS代理代码解析
2023-01-15 00:48:24
网页中的平衡、对比、连贯和留白
2008-11-24 12:11:00
Python面向对象程序设计之类的定义与继承简单示例
2022-03-24 03:00:16
Ubuntu 16.04 LTS中源码安装Python 3.6.0的方法教程
2021-10-19 05:05:53
小学生也能看懂的Golang异常处理recover panic
2024-02-08 20:32:36
Python减肥小工具轻松帮你瘦
2021-07-20 09:54:41
Vue使用JSEncrypt实现rsa加密及挂载方法
2024-06-05 10:02:30
Python的爬虫包Beautiful Soup中用正则表达式来搜索
2022-12-29 07:15:34
正则表达式判断号码靓号类型
2009-10-31 18:48:00
python实现简单的学生成绩管理系统
2023-04-03 01:08:25
C#调用Python模块的方法
2021-04-13 15:29:10
python中pickle模块浅析
2022-02-06 06:27:38
关于keras中卷积层Conv2D的学习记录
2022-07-16 17:33:16