二叉樹中和為某一值的路徑：
輸入一顆二叉樹的跟節(jié)點(diǎn)和一個整數(shù)，打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)形成一條路徑。(注意: 在返回值的list中，數(shù)組長度大的數(shù)組靠前)
思路：
1、二叉樹的前序遍歷，中左右順序
2、把目標(biāo)值target傳進(jìn)去，target-=val
3、target為0并且left和right都為null，達(dá)到葉結(jié)點(diǎn)
4、函數(shù)外部兩個數(shù)組，list數(shù)組存一條路徑，listAll數(shù)組存所有路徑
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)
//如果到了這條路徑的跟結(jié)點(diǎn)，并沒有達(dá)到目標(biāo)，就刪掉最后的結(jié)點(diǎn)，退回上一個結(jié)點(diǎn)
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;
}
以上就是本次內(nèi)容的全部實(shí)例代碼，大家可以本次測試一下，感謝大家對腳本之家的支持。
您可能感興趣的文章:- PHP排序二叉樹基本功能實(shí)現(xiàn)方法示例
- PHP實(shí)現(xiàn)二叉樹深度優(yōu)先遍歷(前序、中序、后序)和廣度優(yōu)先遍歷(層次)實(shí)例詳解
- PHP實(shí)現(xiàn)從上往下打印二叉樹的方法
- PHP獲取二叉樹鏡像的方法
- PHP實(shí)現(xiàn)按之字形順序打印二叉樹的方法
- PHP基于非遞歸算法實(shí)現(xiàn)先序、中序及后序遍歷二叉樹操作示例
- PHP實(shí)現(xiàn)判斷二叉樹是否對稱的方法
- PHP實(shí)現(xiàn)繪制二叉樹圖形顯示功能詳解【包括二叉搜索樹、平衡樹及紅黑樹】
- PHP完全二叉樹定義與實(shí)現(xiàn)方法示例
