php如何实现二叉树中和为某一值的路径（代码）-php教程-PHP中文网

php如何实现二叉树中和为某一值的路径（代码）

不言

发布： 2018-10-11 15:45:31

转载

2385人浏览过

本篇文章给大家带来的内容是关于php如何实现二叉树中和为某一值的路径（代码），有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。

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

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

思路：

1、二叉树的前序遍历，中左右顺序

2、把目标值target传进去，target-=val

立即学习“PHP免费学习笔记（深入）”；

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中文网其它相关文章！