[LeetCode] Path Sum III 二叉樹的路徑和之三

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

這道題讓我們求二叉樹的路徑的和等于一個給定值，說明了這條路徑不必要從根節點開始，可以是中間的任意一段，而且二叉樹的節點值也是有正有負。那麼我們可以用遞歸來做，相當于先序周遊二叉樹，對于每一個節點都有記錄了一條從根節點到目前節點到路徑，同時用一個變量curSum記錄路徑節點總和，然後我們看curSum和sum是否相等，相等的話結果res加1，不等的話我們來繼續檢視子路徑和有沒有滿足題意的，做法就是每次去掉一個節點，看路徑和是否等于給定值，注意最後必須留一個節點，不能全去掉了，因為如果全去掉了，路徑之和為0，而如果假如給定值剛好為0的話就會有問題，整體來說不算一道很難的題，參見代碼如下：

解法一：

我們還可以對上面的方法進行一些優化，來去掉一些不必要的計算，我們可以用哈希表來建立所有的字首路徑之和跟其個數之間的映射，然後看子路徑之和有沒有等于給定值的，參見代碼如下：

解法二：

下面這種方法非常的簡潔，也是利用了前序周遊，對于每個周遊到的節點進行處理，維護一個變量pre來記錄之前路徑之和，然後cur為pre加上目前節點值，如果cur等于sum，那麼傳回結果時要加1，然後對目前節點的左右子節點調用遞歸函數求解，參見代碼如下：

解法三：