輸入一顆二叉樹和一個整數(shù)，打印出二叉樹中結(jié)點值的和為輸入整數(shù)的所有路徑包晰。路徑定義為從樹的根結(jié)點開始往下一直到葉結(jié)點所經(jīng)過的結(jié)點形成一條路徑憨琳。
二叉樹遍歷順序有層次遍歷锰蓬，前中后序遍歷邻储。這里要找出二叉樹的所有的路徑里的節(jié)點的值的和為某個值的所有路徑赋咽。前中后序遍歷可以采用遞歸的方式進(jìn)行但是這里感覺使用起來很困難，因為找的不是一次遍歷吨娜。而是多條路徑脓匿。從上到下分叉后就變?yōu)閮蓷l，但是沒分叉之前的屬于兩條路徑都應(yīng)該包含的部分萌壳。所以自己通過建立一個棧亦镶，通過在必要的時候入棧和出棧日月，根據(jù)棧的元素得到每條路徑袱瓮，并根據(jù)元素的和判斷是否符合條件缤骨。
function FindPath($root, $expectNumber)
{
if($root==null){
return [];
}
$stack = array($root);
$result = array();
while(count($stack)!=0){
$topnode = end($stack);
while ($topnode->left != null || $topnode->right!= null){
if($topnode->left != null){
$stack[] = $topnode->left;
$p = $topnode->left;
$topnode->left = null;
$topnode = $p;
}elseif ($topnode->right != null){
$stack[] = $topnode->right;
$p = $topnode->right;
$topnode->right = null;
$topnode = $p;
}
}
$sum = 0;
$sub_paths = array();
foreach ($stack as $node){
$sum += $node->val;
$sub_paths[] = $node->val;
if($sum>$expectNumber){
break;
}
}
if($sum==$expectNumber){
$result[] = $sub_paths;
}
while($topnode->left == null && $topnode->right== null){
array_pop($stack);
if(count($stack)==0){
return $result;
}
$topnode = end($stack);
}
}
return result;
}
首先把樹的根節(jié)點壓入棧內(nèi)，根據(jù)棧是否為空作為遍歷結(jié)束條件尺借。循環(huán)中每次都取棧頂元素绊起。如果棧頂元素的左節(jié)點或者右節(jié)點不為空就進(jìn)行壓入，先判斷左節(jié)點燎斩，保證每次訪問路徑是從左邊的節(jié)點到右邊的節(jié)點保存的虱歪，先判斷右邊和先判斷左邊沒有本質(zhì)區(qū)別。在壓入棧后栅表，將節(jié)點的左節(jié)點或者右節(jié)點賦值為null笋鄙，是為了斷開連接。防止出現(xiàn)死循環(huán)怪瓶，在斷開連接前都會先得到后面指向的節(jié)點萧落。通過這層循環(huán)，就能得到一條路徑了洗贰，因為只有葉子節(jié)點的左節(jié)點和右節(jié)點才會同時為null找岖。中間部分就是訪問當(dāng)前棧內(nèi)的元素得到本次的路徑根據(jù)條件判斷是否需要保存。路徑保存后需要彈出棧敛滋，出棧條件是左右子樹都為空许布，有兩種情況，第一種就是葉子節(jié)點绎晃，葉子節(jié)點就是上面路徑的最后一個節(jié)點蜜唾，自然要彈出，第二種就是上面的while循環(huán)入棧前通過斷開連接操作賦值為null造成的庶艾，這里是表明該節(jié)點的左右分叉的路徑都已經(jīng)輸出了灵妨，這樣自然也要彈出。這樣最后棧頂節(jié)點就是沒有分叉的路徑還存在沒有輸出完的節(jié)點落竹∶诨簦總體就是利用棧和通過賦值null操作標(biāo)記是否訪問來得到每條路徑并且根據(jù)路徑的值的和來完成求解的。
