php实现二叉树中和为某一值的路径技巧

发布时间：2022-06-30 15:10:39 所属栏目：PHP教程来源：互联网

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

　　二叉树中和为某一值的路径：

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

　　思路：

　　1、二叉树的前序遍历，中左右顺序

　　2、把目标值target传进去，target-=val

　　3、target为0并且left和right都为null，达到叶结点

　　4、函数外部两个数组，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;
　　    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->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();
　　
　　    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读取文件内容几种正
php中读取大文件实现方	php打开远程文件的方法