Comment implémenter un chemin qui totalise une certaine valeur dans un arbre binaire en PHP (code)

Le contenu de cet article explique comment PHP implémente le chemin (code) qui neutralise un arbre binaire à une certaine valeur. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer. .

Le chemin dont la somme dans l'arbre binaire est une certaine valeur :

Saisissez le nœud talon d'un arbre binaire et un entier, et imprimez tous les nœuds de l'arbre binaire dont la somme est le chemin entier d’entrée. Un chemin est défini comme un chemin partant du nœud racine de l’arbre et descendant jusqu’aux nœuds en passant par les nœuds feuilles. (Remarque : dans la liste des valeurs de retour, le tableau avec la plus grande longueur de tableau est placé en premier)

Idées :

1 Parcours pré-commandé de l'arbre binaire, ordre gauche et droite.

2 , transmettez la valeur cible target, target-=val

3 target est 0 et les deux gauche et droite sont nulles, atteignant le nœud feuille

4. Deux tableaux en dehors de la fonction, list Le tableau stocke un chemin et le tableau listAll stocke tous les chemins

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;
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!