php實(shí)現(xiàn)二叉樹中和為某一值的路徑方法
二叉樹中和為某一值的路徑:
輸入一顆二叉樹的跟節(jié)點(diǎn)和一個(gè)整數(shù),打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的結(jié)點(diǎn)形成一條路徑。(注意: 在返回值的list中,數(shù)組長(zhǎng)度大的數(shù)組靠前)
思路:
1、二叉樹的前序遍歷,中左右順序
2、把目標(biāo)值target傳進(jìn)去,target-=val
3、target為0并且left和right都為null,達(dá)到葉結(jié)點(diǎn)
4、函數(shù)外部?jī)蓚€(gè)數(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),并沒(méi)有達(dá)到目標(biāo),就刪掉最后的結(jié)點(diǎn),退回上一個(gè)結(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í)例代碼,大家可以本次測(cè)試一下,感謝大家對(duì)腳本之家的支持。
- 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)判斷二叉樹是否對(duì)稱的方法
- PHP實(shí)現(xiàn)繪制二叉樹圖形顯示功能詳解【包括二叉搜索樹、平衡樹及紅黑樹】
- PHP完全二叉樹定義與實(shí)現(xiàn)方法示例
相關(guān)文章
Zend Framework教程之Zend_Controller_Plugin插件用法詳解
這篇文章主要介紹了Zend Framework教程之Zend_Controller_Plugin插件用法,結(jié)合實(shí)例形式詳細(xì)分析了Zend_Controller_Plugin插件的原理,使用方法與相關(guān)注意事項(xiàng),需要的朋友可以參考下2016-03-03PHP 獲取視頻時(shí)長(zhǎng)的實(shí)例代碼
本文通過(guò)實(shí)例代碼給大家介紹了php獲取視頻時(shí)長(zhǎng)的相關(guān)知識(shí),非常不錯(cuò),具有一定的參考借鑒價(jià)值,需要的朋友參考下吧2018-07-07thinkPHP顯示不出驗(yàn)證碼的原因與解決方法分析
這篇文章主要介紹了thinkPHP顯示不出驗(yàn)證碼的原因與解決方法,結(jié)合具體實(shí)例形式分析了thinkPHP關(guān)于驗(yàn)證碼顯示的相關(guān)配置方法與注意事項(xiàng),需要的朋友可以參考下2017-05-05php加水印的代碼(支持半透明透明打水印,支持png透明背景)
一個(gè)簡(jiǎn)單的打水印代碼(圖片水印),支持水印透明度設(shè)置,也支持png透明背景格式圖片打水印2013-01-01