PHP의 이진 트리에서 특정 값을 합산하는 경로를 구현하는 방법(코드)

이 문서의 내용은 바이너리 트리를 특정 값으로 중화하는 경로(코드)를 구현하는 방법에 대한 내용입니다. 필요한 친구가 참고할 수 있기를 바랍니다.

이진 트리의 합이 특정 값인 경로:

이진 트리의 힐 노드와 정수를 입력하고 노드 값의 합이 입력 정수인 이진 트리의 모든 경로를 인쇄합니다. 경로는 트리의 루트 노드에서 시작하여 리프 노드를 통과하는 노드로 내려가는 경로로 정의됩니다. (참고: 반환 값 목록에서 배열 길이가 더 큰 배열이 먼저 배치됩니다.)

아이디어:

1. 이진 트리의 선순서 순회, 중간 및 왼쪽 순서

2. target in, target-=val

3. 대상은 0이고 왼쪽과 오른쪽 모두 null이며 리프 노드

4에 도달합니다. 목록 배열은 하나의 경로를 저장하고 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!