php实现二叉树中和为某一值的路径方法

php  /  管理员 发布于 7年前   156

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

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的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

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

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

以上就是本次内容的全部实例代码，大家可以本次测试一下，感谢大家对AIDI的支持。

您可能感兴趣的文章:

• PHP排序二叉树基本功能实现方法示例
• PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
• PHP实现从上往下打印二叉树的方法
• PHP获取二叉树镜像的方法
• PHP实现按之字形顺序打印二叉树的方法
• PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例
• PHP实现判断二叉树是否对称的方法
• PHP实现绘制二叉树图形显示功能详解【包括二叉搜索树、平衡树及红黑树】
• PHP完全二叉树定义与实现方法示例