php实现二叉树中和为某一值的路径方法
作者:laozhang 发布时间:2023-07-04 20:29:08
标签: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;
}
0
投稿
猜你喜欢
- Array(数组)内部机制在 Go 语言中数组是固定长度的数据类型,它包含相同类型的连续的元素,这些元素可以是内建类型,像数字和字符串,也可
- 本文将介绍PHP中单引号和双引号的区别。PHP中单引号和双引号简介在 PHP 中,我们使用引号来指定值是字符串文字。有两种不同类型的报价。它
- 大家做网站,特别是自己写的代码,常常担心被一些黑客入侵服务器,从而导致网站代码被盗,给自己带来一些损失。那么我们怎么样做,就算黑客盗了你的代
- 什么是CSS Sprites?“Sprite”(精灵)这个词在计算机图形学中有它独特的定义,由于游戏、视频等画质越来越高,必须有一种技术可以
- 如何在页面中快捷地添加翻页按钮? 先编写一个nextprev.inc文件,再将代码<
- 很早就听说韩国网站的设计师们很会利用空间,来创造更多的信息承载量.最近浏览了几个韩国SHOPPING网站果不其然,就拿小小的广告轮播来说,非
- 代码如下:---在仓储管理中经常会碰到的一个问题 一、关于LIFO与FIFO的简单说明 ---FIFO: First in, First o
- 网页制作中用到的特效字,你一定是用图象处理软件制作的吧!告诉你,不用图象处理软件,我也能做出漂亮的特效字来,你看,阴影字我就是这样做出来的。
- 本文说明向外扩展数据库系统的两个选项,从而实现更高的可扩展性:水平数据划分和垂直数据划分当我提到向外扩展数据库系统时,我实际上只是讨论对数据
- RedHat 9.0下自带的mysql rpm包为mysql-3.23.54a-11.i386.rpm,如果在你安装操作系统时没有安装mys
- 在document.form1.submit();后加document.body.innerHtml = "W
- 随着对Dreamweaver cs3中集成Spry功能的深入学习,了解并掌握到Spry框架的一些功能模块,其中就有通过Dreamweaver
- 代码如下:<% FunctIon DownloadFIle(StrFIle) StrFIlename=StrFIle Response
- 一直以来,ACCESS数据库中的申报数据在分公司与总公司之间传递,用EXCEL或DBASE、TXT甚至ACCESS等格式,我总觉得不太理想。
- 我们现在回到函数上。记得我们用 SUM 这个指令来算出所有的 Sales (营业额)吧!如果我们的需求变成是要算出每一间店 (store_n
- 当管理SQL Server内在的帐户和密码时,我们很容易认为这一切都相当的安全。但实际上并非如此。在这里,我们列出了一些对于SQL Serv
- 几天前,想把上个月校园招聘的餐旅费报销一下。结果在公司内网的报销系统折腾了三个半小时才搞定。看看自己报销的金额:802块。觉得挺无奈,花了三
- asp如何将RGB颜色转化成到16进制的?在R G B中输入小于255的数字点击观看即可转换成#开通的16进制。代码如下:<%R_RG
- 前言原子操作这是Java多线程编程的老生常谈了。所谓原子操作是指不会被线程调度机制打断的操作;这种操作一旦开始,就一直运行到结束,中间不会有
- 如果你已经理解了block formatting contexts那么请继续,否则请先看看这篇文章。Overflow能够做一些很牛掰的事情,