[程式員面試題精選100題]4.二叉樹中和為某一值的所有路徑

輸入一個整數和一棵二進制樹。從樹的根結點開始往下通路一直到葉結點所經過的所有結點形成一條路徑。

列印出和與輸入整數相等的所有路徑。

例如輸入整數22和如下二進制樹

                                            10

                                           /   \

                                          5     12

                                        /   \   

                                     4     7 

則列印出兩條路徑：10, 12和10, 5, 7。

這是百度的一道筆試題，考查對樹這種基本資料結構以及遞歸函數的了解。

當通路到某一結點時，把該結點添加到路徑上，并累加目前結點的值。

如果目前結點為葉結點并且目前路徑的和剛好等于輸入的整數，則目前的路徑符合要求，我們把它列印出來。

如果目前結點不是葉結點，則繼續通路它的子結點。目前結點通路結束後，遞歸函數将自動回到父結點。

是以我們在函數退出之前要在路徑上删除目前結點并減去目前結點的值，以確定傳回父結點時路徑剛好是根結點到父結點的路徑。

我們不難看出儲存路徑的資料結構實際上是一個棧結構，因為路徑要與遞歸調用狀态一緻，而遞歸調用本質就是一個壓棧和出棧的過程。

測試：

10 5 4 -1 -1 7 -1 -1 12 -1 -1

輸出：

10->5->7

10->12