PHP でバイナリ ツリーに合計が特定の値になるパスを実装する方法 (コード)

この記事の内容は、バイナリツリーを特定の値に無力化するパス (コード) を PHP がどのように実装するかについてです。特定の参照値があります。必要な友人はそれを参照できます。お役に立てば幸いです。 . .

二分木の合計が特定の値になるパス:

二分木の次のノードと整数を入力し、二分木のすべてのノードを出力します。合計が入力整数となるツリー。パスは、ツリーのルート ノードから始まり、リーフ ノードを通過してノードに至るパスとして定義されます。 (注: 戻り値のリストでは、配列長の大きい配列が最初に配置されます)

アイデア:

1. バイナリ ツリーの事前順序トラバーサル (左順と右順)

2 、ターゲット値 target を渡します。 target-=val

3、target は 0、左右両方とも null、リーフ ノード

4 に到達、2 つの配列関数の外側では、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 中国語 Web サイトの他の関連記事を参照してください。