欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-05-05 13:00:04
二叉树中和为某一值的路径: 输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条...

二叉树中和为某一值的路径:

输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的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;

}

以上就是本次内容的全部实例代码,大家可以本次测试一下,感谢大家对的支持。