So implementieren Sie einen Pfad, der in einem Binärbaum einen bestimmten Wert ergibt, in PHP (Code)

Der Inhalt dieses Artikels befasst sich damit, wie PHP den Pfad (Code) implementiert, der einen Binärbaum auf einen bestimmten Wert neutralisiert. Ich hoffe, dass er für Sie hilfreich ist . .

Der Pfad, dessen Summe im Binärbaum einen bestimmten Wert hat:

Geben Sie den Fersenknoten eines Binärbaums und eine Ganzzahl ein und drucken Sie alle Knoten im Binärbaum aus deren Summe der Eingabe-Ganzzahlpfad ist. Ein Pfad ist definiert als ein Pfad, der vom Wurzelknoten des Baums beginnt und nach unten zu den Knoten führt, die durch die Blattknoten verlaufen. (Hinweis: In der Liste der Rückgabewerte wird das Array mit der größeren Array-Länge zuerst platziert)

Ideen:

1. Vorbestellungsdurchlauf des Binärbaums, linke und rechte Reihenfolge

2, übergeben Sie den Zielwert target-=val

3 target ist 0 und sowohl links als auch rechts sind null und erreichen den Blattknoten

4. Zwei Arrays außerhalb der Funktion, list Das Array speichert einen Pfad und das listAll-Array speichert alle Pfade

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

Das obige ist der detaillierte Inhalt vonSo implementieren Sie einen Pfad, der in einem Binärbaum einen bestimmten Wert ergibt, in PHP (Code). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!