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)

相关推荐

  • PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解

    PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解

    本文实例讲述了PHP实现二叉树深度优先遍历(前序.中序.后序)和广度优先遍历(层次).分享给大家供大家参考,具体如下: 前言: 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次.要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历.中序遍历.后序遍历.具体说明如下: 前序遍历:根节点->左子树->右子树 中序遍历:左子树->根节点->右子树 后序遍历:左子树->右子树->根节点 广度优先遍历:又叫层次遍历,从上往下对每一层依

  • PHP获取二叉树镜像的方法

    本文实例讲述了PHP获取二叉树镜像的方法.分享给大家供大家参考,具体如下: 问题 操作给定的二叉树,将其变换为源二叉树的镜像. 解决思路 翻转二叉树,有递归和非递归两种方式,非递归就是使用队列. 实现代码 <?php /*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; } }*/ function Mirror(&$

  • PHP完全二叉树定义与实现方法示例

    PHP完全二叉树定义与实现方法示例

    本文实例讲述了PHP完全二叉树定义与实现方法.分享给大家供大家参考,具体如下: 若设二叉树的深度为h,除第 h 层外,其它各层 (1-h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树. PHP代码实现(暂时实现添加节点.层次遍历节点,删除节点后续更新) <?php class Node{ public $value; public $leftNode; public $rightNode; } /* 找到空节点 */ function findEmpyt

  • PHP排序二叉树基本功能实现方法示例

    本文实例讲述了PHP排序二叉树基本功能实现方法.分享给大家供大家参考,具体如下: 这里演示了排序二叉树节点的插入,中序遍历,极值的查找和特定值的查找的功能. 基本没有提供什么概念和定义.建议先简单了解一下本文提供的几个概念在来看本文. 实际上,只是简单的提供了代码,注释也很少,各位辛苦了. 二叉树:在计算机科学中,二叉树是每个节点最多有两个子树的树结构. 排序二叉树: 左孩子节点的值小于父节点的值,右孩子节点的值大于父节点的值. 几个概念: 根节点 叶子节点 左子树 右子树 中序遍历 前序遍历

  • PHP实现从上往下打印二叉树的方法

    本文实例讲述了PHP实现从上往下打印二叉树的方法.分享给大家供大家参考,具体如下: 问题 从上往下打印出二叉树的每个节点,同层节点从左至右打印. 解决思路 每层树从左到右打印,所以需要将节点的左右子树存起来,因为先进先出,所以用队列. 实现代码 /*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; } }*/ function

  • PHP实现按之字形顺序打印二叉树的方法

    本文实例讲述了PHP实现按之字形顺序打印二叉树的方法.分享给大家供大家参考,具体如下: 问题 请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推. 解决思路 使用两个栈 实现代码 <?php /*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $

  • PHP实现判断二叉树是否对称的方法

    本文实例讲述了PHP实现判断二叉树是否对称的方法.分享给大家供大家参考,具体如下: 问题 请实现一个函数,用来判断一颗二叉树是不是对称的.注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的. 题解 递归判断二叉树两侧. 实现代码: <?php /*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; } }*/ func

  • PHP实现绘制二叉树图形显示功能详解【包括二叉搜索树、平衡树及红黑树】

    PHP实现绘制二叉树图形显示功能详解【包括二叉搜索树、平衡树及红黑树】

    本文实例讲述了PHP实现绘制二叉树图形显示功能.分享给大家供大家参考,具体如下: 前言: 最近老师布置了一个作业:理解并实现平衡二叉树和红黑树,本来老师是说用C#写的,但是我学的C#基本都还给老师了,怎么办?那就用现在最熟悉的语言PHP来写吧! 有一个问题来了,书上在讲解树的时候基本上会给出形象的树形图.但是当我们自己试着实现某种树,在调试.输出的时候确只能以字符的形式顺序地输出.这给调试等方面带来了很大的不便.然后在各种百度之后,我发现利用PHP实现二叉树的图形显示的资源几乎是零!好吧,那我就

  • PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例

    本文实例讲述了PHP基于非递归算法实现先序.中序及后序遍历二叉树操作.分享给大家供大家参考,具体如下: 概述: 二叉树遍历原理如下: 针对上图所示二叉树遍历: 1. 前序遍历:先遍历根结点,然后遍历左子树,最后遍历右子树. ABDHECFG 2.中序遍历:先遍历左子树,然后遍历根结点,最后遍历右子树. HDBEAFCG 3.后序遍历:先遍历左子树,然后遍历右子树,最后遍历根节点. HDEBFGCA 实现方法: 先序遍历:利用栈先进后出的特性,先访问根节点,再把右子树压入,再压入左子树.这样取出的

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

    二叉树中和为某一值的路径: 输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径.路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径.(注意: 在返回值的list中,数组长度大的数组靠前) 思路: 1.二叉树的前序遍历,中左右顺序 2.把目标值target传进去,target-=val 3.target为0并且left和right都为null,达到叶结点 4.函数外部两个数组,list数组存一条路径,listAll数组存所有路径 FindPath(roo

  • Python编程求解二叉树中和为某一值的路径代码示例

    题目描述 输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径.路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径. 思路:首先要理解题意,是从根节点往子节点连. 1.如果只有根节点或者找到叶子节点,我们就把其对应的val值返回 2.如果不是叶子节点,我们分别对根节点的左子树.右子树进行递归,直到找到叶子结点.然后遍历把叶子结点和父节点对应的val组成的序列返回上一层:如果没找到路径,其实也返回了序列,只不过是[] 代码如下: # -*- coding:utf-

  • C++实现查找二叉树中和为某一值的所有路径的示例

    C++实现查找二叉树中和为某一值的所有路径的示例

    从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径. 打印出和与输入整数相等的所有路径. 例如 输入整数22和如下二元树 则打印出两条路径:10, 12和10, 5, 7. 先序遍历树即可得到结果. 算法: FindPath(BTree * root,int sum,int target,Stack * s) 用来计算,sum为栈中的元素的和,target为目标值. 到达一个节点之后计算当前节点和sum的和,如果为target,输出路径返回,如果大于target,则直接返回,如果小

  • 使用递归遍历对象获得value值的实现方法

    一般要用到递归,就要判断对象是否和父类型是否一样 这里演示简单的对象递归,还有数组递归类似. var obj = { a:{w:1,y:2,x:3}, b:{s:4,j:5,x:6}, c:{car:7,cat:8,mao:9} } function f(s){ for(var i in s){ if(typeof s[i]=="object"){ f(s[i]) }else{ console.log(s[i]); } } } f(obj); 返回结果:1,2,3,4,5,6,7,8,

  • 对象转换为原始值的实现方法

    首先,我们要明白原始值得概念 原始值 存储在栈(stack)中的简单数据段,也就是说,它们的值直接存储在变量访问的位置. 引用值 存储在堆(heap)中的对象,也就是说,存储在变量处的值是一个指针(point),指向存储对象的内存处 ----引用了w3c里的概念 原始值,简单点理解就是 null  undefined string number Boolean 这些 对象转换为boolean相对简单 所有的对象(包括数组和函数)都转换成true,包装对象从也是对象,也转换为true 书上是这么说

  • Angular中ng-options下拉数据默认值的设定方法

    Angular中ng-options下拉数据默认值的设定方法

    今天学习了一下Angular中ng-options下拉数据默认值的设定方法,留个笔记 直接上代码 <div class="form-group"> <label class="col-sm-2 control-label">教师</label> <div class="col-sm-10"> <select style="display:block; width:100%; heig

  • JS动态给对象添加属性和值的实现方法

    如下所示: var obj={}; for(var i=0;i<10;i++){ eval("obj.p"+i+"="+i); } 以上就是小编为大家带来的JS动态给对象添加属性和值的实现方法全部内容了,希望大家多多支持我们~

  • JS清除字符串中重复值的实现方法

    本文实例讲述了JS清除字符串中重复值的实现方法.分享给大家供大家参考,具体如下: /// <summary> /// 清除字符串中重复的值 /// </summary> /// <param name="Text">字符串</param> /// <param name="Label">标签(如:| ,)</param> function FilterRepeatStr(Text, Label)

  • javascript使用for循环批量注册的事件不能正确获取索引值的解决方法

    本文实例讲述了javascript使用for循环批量注册的事件不能正确获取索引值的解决方法.分享给大家供大家参考.具体分析如下: 可能不少朋友会遇到一个问题,那就是当使用for循环批量注册事件处理函数,然后最后通过事件处理函数获取当前元素的索引值的时候会失败,先看一段代码实例: 复制代码 代码如下: <!DOCTYPE html> <html> <head> <meta charset=" utf-8"> <meta name=&q

  • JavaScript中无法通过div.style.left获取值的解决方法

    JavaScript中无法通过div.style.left获取值的解决方法

    一.问题总结: 样式必须直接写在元素内部才能通过div.style.left直接获取属性值(也就是必须是内联样式才行),定义在css中的样式不能通过这种方式获取. 让元素移动到200停止 setTimeout ( function () { var div = document.getElementById("div4"); //var left = parseInt(div.style.left) + 5; var left = div.offsetLeft + 5; div.sty

随机推荐