php如何实现二叉树中和为某一值的路径（代码）

内容导读

收集整理的这篇技术教程文章主要介绍了php如何实现二叉树中和为某一值的路径（代码），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2199字，纯文字阅读大概需要4分钟。

内容图文

本篇文章给大家带来的内容是关于php如何实现二叉树中和为某一值的路径（代码），有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。

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

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

<?phpclass 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如何实现二叉树中和为某一值的路径（代码）的详细内容，更多请关注Gxl网其它相关文章！

内容总结

以上是为您收集整理的php如何实现二叉树中和为某一值的路径（代码）全部内容，希望文章能够帮你解决php如何实现二叉树中和为某一值的路径（代码）所遇到的程序开发问题。 如果觉得技术教程内容还不错，欢迎将网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。