扣丁学堂PHP培训简述PHP实现二叉树中和为某一值的路径方法

2019-05-15 11:17:39 3835浏览

本篇文章扣丁学堂PHP培训小编给读者们分享一下PHP实现二叉树中和为某一值的路径方法，对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;

}

想要了解更多关于PHP开发方面内容的小伙伴，请关注扣丁学堂PHP培训官网、微信等平台，扣丁学堂IT职业在线学习教育有专业的PHP讲师为您指导，此外扣丁学堂老师精心推出的PHP视频教程定能让你快速掌握PHP从入门到精通开发实战技能。扣丁学堂PHP技术交流群：374332265。

扣丁学堂微信公众号 HTML5前端开发VIP免费公开课

【关注微信公众号获取更多学习资料】【扫码进入HTML5前端开发VIP免费公开课】

查看更多关于“php培训资讯”的相关文章>>

标签: PHP培训 PHP基础教程 PHP学习视频 PHP教学视频 PHP入门教程 PHP教程视频 PHP在线学习 PHP在线视频 PHP在线教程扣丁学堂PHP培训

上一篇扣丁学堂PHP培训分享PHP使Laravel为JSON REST API返回自定义错误的问题下一篇扣丁学堂PHP培训简述PHP中使用CURL发送get/post请求上传图片批处理功能

扣丁学堂PHP培训简述PHP实现二叉树中和为某一值的路径方法

热门专区

课程推荐