437. 路徑總和 III

給定一個二叉樹，它的每個結(jié)點都存放著一個整數(shù)值。

找出路徑和等于給定數(shù)值的路徑總數(shù)。

路徑不需要從根節(jié)點開始，也不需要在葉子節(jié)點結(jié)束，但是路徑方向必須是向下的（只能從父節(jié)點到子節(jié)點）。

二叉樹不超過1000個節(jié)點，且節(jié)點數(shù)值范圍是 [-1000000,1000000] 的整數(shù)。

示例：

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

返回 3。和等于 8 的路徑有:

1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11

雙重遞歸

/*
    思路：
        1.dfs是求從根節(jié)點出發(fā)到葉子節(jié)點滿足條件的路徑總數(shù)
        2.將給定的二叉樹看成三個部分：根節(jié)點、左子樹、右子樹
        3.三部分可以看成一個遞歸結(jié)構(gòu)，先求從根節(jié)點出發(fā)滿足條件的路徑總數(shù)(dfs(root))，
          再遞歸求左子樹(pathSum(root.left))，遞歸求右子樹(pathSum(root.right))
    
    總結(jié)：
        1.雙重遞歸，從全局找外層遞歸(如思路中的三個部分)，再從部分中找內(nèi)層遞歸(如思路中的dfs)
*/

class Solution {
    private int count = 0; //存放結(jié)果
    public int pathSum(TreeNode root, int sum) {
        if(root == null) return 0;
        dfs(root, sum); //求從根節(jié)點出發(fā)滿足條件的路徑總數(shù)
        pathSum(root.left, sum); //遞歸求左子樹
        pathSum(root.right, sum); //遞歸求右子樹
        return count;
    }
    
    private void dfs(TreeNode root, int sum){
        if(root == null) return;
        sum -= root.val;
        if(sum == 0) count++; //滿足條件結(jié)果加一
        dfs(root.left, sum); //繼續(xù)往左子樹找
        dfs(root.right, sum); //繼續(xù)往右子樹找
    }
}

單重遞歸

/*
    思路：
        1.用雙重遞歸會重復(fù)計算很多次，其實我們只用單遞歸就可以解決，
          不妨將已經(jīng)走過的路徑值保存到book數(shù)組
        2.到i節(jié)點，就可以根據(jù)book倒序遍歷，找到從i節(jié)點到根節(jié)點滿足條件的路徑總數(shù)
        3.遞歸到最底層也就是葉子節(jié)點時，找出葉子節(jié)點到根節(jié)點的滿足條件的路徑總數(shù)之后，
          需要將book數(shù)組回溯到上一層的狀態(tài)，以便從上一層繼續(xù)尋找
    
    總結(jié)：
        1.將已經(jīng)求出的值保存，當(dāng)下次遞歸時可以直接使用，
          省去了重復(fù)計算浪費的時間，相當(dāng)于用空間換取時間
        2.遞歸返回到上層時，我們有時需要原來上層遞歸的狀態(tài)，這時就需要用到回溯
*/

class Solution {
    
    private int count = 0; //存放結(jié)果
    public int pathSum(TreeNode root, int sum) {
        dfs(root, sum, new ArrayList<Integer>());
        return count;
    }
    
    private void dfs(TreeNode root, int sum, ArrayList<Integer> book){
        if(root == null) return;
        
        book.add(root.val); //加入當(dāng)前節(jié)點的值
        int cur_sum = 0;
        for(int i = book.size() - 1; i >= 0; i--){ //從當(dāng)前節(jié)點往根節(jié)點尋找滿足條件的路徑總數(shù)
            cur_sum += book.get(i);
            if(cur_sum == sum) count++;
        }
        
        dfs(root.left, sum, book); //遞歸求左子樹
        dfs(root.right, sum, book); //遞歸求右子樹
         
        book.remove(book.size() - 1); //回溯到上一次的狀態(tài)，以便繼續(xù)尋找
    }
}