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

[PHP]算法-二叉树中和为某一值的路径的PHP实现

程序员文章站 2022-04-30 09:46:58
二叉树中和为某一值的路径: 输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中,数组长度大的数组靠前) 思路: 1.二叉树的前序遍历,中左右顺序 2.把目标值target传... ......
二叉树中和为某一值的路径:

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