題目描述

給定一個(gè)二叉樹，它的每個(gè)結(jié)點(diǎn)都存放著一個(gè)整數(shù)值。
找出路徑和等于給定數(shù)值的路徑總數(shù)。
路徑不需要從根節(jié)點(diǎn)開始，也不需要在葉子節(jié)點(diǎn)結(jié)束，但是路徑方向必須是向下的（只能從父節(jié)點(diǎn)到子節(jié)點(diǎn)）。
二叉樹不超過1000個(gè)節(jié)點(diǎn)，且節(jié)點(diǎn)數(shù)值范圍是 [-1000000,1000000] 的整數(shù)。
437. 路徑之和Ⅲ

解法1 遞歸

用了兩個(gè)遞歸，第一個(gè)遞歸是算給定節(jié)點(diǎn)為根的樹中有多少滿足條件的路徑；第二個(gè)遞歸是二叉樹的每個(gè)節(jié)點(diǎn)都執(zhí)行一次第一個(gè)遞歸。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //用于保存最后的路徑總數(shù)
    int res = 0;

    public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        //helper函數(shù)計(jì)算輸入節(jié)點(diǎn)有多少條符合條件路徑
        helper(root, sum);
        //左孩子
        pathSum(root.left, sum);
        //右孩子
        pathSum(root.right, sum);
        return res;
    }

    public void helper(TreeNode root, int sum) {
        if (root == null) {
            return;
        }
        //每遍歷到一個(gè)節(jié)點(diǎn)，sum減去這個(gè)節(jié)點(diǎn)值
        sum -= root.val;
        if (sum == 0) {
            res++;
            /*
             *這里一開始我寫了條return，但是沒過，發(fā)現(xiàn)在非葉
             *子節(jié)點(diǎn)時(shí)sum到0就return而不往下遍歷的話，會(huì)遺漏后續(xù)節(jié)點(diǎn)中相加為0的 
             *情況。例如 [1,-2,-3,1,3,-2,null,-1] 的二叉樹，[1, -2]是，[1, -2, 1, -1]也是，
             *如果這里有return，后面這條就遞歸不出來。
            */
        }
        helper(root.left, sum);
        helper(root.right, sum);
    }
}

解法2 遞歸加回溯

提交了第一種解法的代碼后，去leetcode后臺(tái)看了下數(shù)據(jù)，發(fā)現(xiàn)有人提交了3ms的結(jié)果（解法1 28ms），里面有更為驚艷的想法。
這篇講得很清楚。