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

发布时间：2020-05-25 03:10:25 所属栏目：PHP 来源：互联网

导读：二叉树中和为某一值的路径：输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)思路：1.二叉树的前序

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意:<span style="color: #000000"> 在返回值的list中，数组长度大的数组靠前)
思路：

1.<span style="color: #000000">二叉树的前序遍历，中左右顺序

2.把目标值target传进去，target-=<span style="color: #000000">val

3.<span style="color: #000000">target为0并且left和right都为null，达到叶结点

4.<span style="color: #000000">函数外部两个数组，list数组存一条路径，listAll数组存所有路径
FindPath(root,<span style="color: #000000">target)

<span style="color: #0000ff">if root==<span style="color: #0000ff">null <span style="color: #0000ff">return<span style="color: #000000"> listAll

<span style="color: #0000ff">list[]=root.<span style="color: #000000">val

target-=root.<span style="color: #000000">val

<span style="color: #0000ff">if target==0 && root->left==<span style="color: #0000ff">null && root->right==<span style="color: #0000ff">null<span style="color: #000000">

listAll[]=<span style="color: #0000ff">list<span style="color: #000000">

FindPath(root->left,<span style="color: #000000">target)

FindPath(root->right,<span style="color: #000000">target)

<span style="color: #008000">//<span style="color: #008000">如果到了这条路径的跟结点，并没有达到目标，就删掉最后的结点，退回上一个结点

<span style="color: #008080">array_pop(<span style="color: #0000ff">list<span style="color: #000000">)

<span style="color: #0000ff">return listAll

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

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,&$list,&$listAll)
{

    </span><span style="color: #0000ff"&gt;if</span>(<span style="color: #800080"&gt;$root</span>==<span style="color: #0000ff"&gt;null</span><span style="color: #000000"&gt;){
            </span><span style="color: #0000ff"&gt;return</span> <span style="color: #800080"&gt;$listAll</span><span style="color: #000000"&gt;;
    }   
    </span><span style="color: #800080"&gt;$target</span>-=<span style="color: #800080"&gt;$root</span>-><span style="color: #000000"&gt;val;
    </span><span style="color: #800080"&gt;$list</span>[]=<span style="color: #800080"&gt;$root</span>-><span style="color: #000000"&gt;val;
    </span><span style="color: #0000ff"&gt;if</span>(<span style="color: #800080"&gt;$target</span>==0 &amp;&amp; <span style="color: #800080"&gt;$root</span>->left==<span style="color: #0000ff"&gt;null</span> &amp;&amp; <span style="color: #800080"&gt;$root</span>->right==<span style="color: #0000ff"&gt;null</span><span style="color: #000000"&gt;){

            </span><span style="color: #800080"&gt;$listAll</span>[]=<span style="color: #800080"&gt;$list</span><span style="color: #000000"&gt;;
    }   
    dfs(</span><span style="color: #800080"&gt;$root</span>->left,<span style="color: #800080"&gt;$listAll</span><span style="color: #000000"&gt;);
    dfs(</span><span style="color: #800080"&gt;$root</span>->right,<span style="color: #800080"&gt;$listAll</span><span style="color: #000000"&gt;);
    </span><span style="color: #008080"&gt;array_pop</span>(<span style="color: #800080"&gt;$list</span><span style="color: #000000"&gt;);
    </span><span style="color: #0000ff"&gt;return</span> <span style="color: #800080"&gt;$listAll</span><span style="color: #000000"&gt;;

}

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!