PathSumIII [source code]

public class PathSumIII {
static

public class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        return collect(root, sum);
    }

    private int collect(TreeNode root, int sum) {
        if (root == null) return 0;
        return collect(root.left, sum) + dfs(root, sum) + collect(root.right, sum);
    }

    private int dfs(TreeNode root, int sum) {
        if (root == null) return 0;
        int res = 0;
        if (root.val == sum) res += 1;
        res += dfs(root.left, sum - root.val) + dfs(root.right, sum - root.val);
        return res;
    }
}

    public static void main(String[] args) {
        PathSumIII.Solution tester = new PathSumIII.Solution();
    }
}

这个题目还是花了不少时间;

拿到一个 tree 的问题, 我们有两个思考角度, 要么是 DFS, 要么是recursion.
一般来说 recursion 是主要思路(DFS主要是在你想要用 stream 类算法的思路来理解这个 traverse 的过程的时候才比较有用);

这一题的话, 我们走 recursion 的思路, 那么首先我们要找到参数(适合变化的, 可以反映 problem 的 size 等性质的变化的), 以及一个返回值(需要具有 DP property);
这个题目就有点像 diameter 那一题, 要找的这个path 看起来就好像动来动去, 完全无法确定在哪里. 如果我们单纯的让这个返回值就是number of matching paths in the subtree rooted at node, 那么这个返回值是不具有 DP Property 的.
类似那里同样的方法, 这里的技巧是, 加上additional constraint: 让返回值成为number of satisfying paths starting from the root, 正好, 我们这里要找的 path 全都是 downward 的;

下一个问题就是, 我们找到这样一个 DP value 之后, 我们怎样转化到我们最后的想要的结果? 答案就是全部求和就行了, 这个过程在 tree 里面需要另外一个单独的 recursion. 所以最后用了两个 recursion, 这个可能也是为什么这个算法最终速度不太优秀; 不过这个题目说了 node 数量不超过1000, 感觉是故意告诉我们, 不一定非要追求 linear. 这里两个 recursion, 最后的速度是 N^2;

为什么求和可以? 因为我们规定的是path starting from root, 而不是单纯的passing root, 所以一个 path 一定唯一对应一个 root. 只要你找到每一个 root 的这个 path 的数量, 加起来, 就肯定不会有重复; 这个有另外一个隐含的原因是:

DFS没有重复

我们当初425学 backtracking 的时候就知道, backtrack 的一大特性就是不能有重复;

另外, 这里的 DFS 写的时候也碰到一点小的新体验. 以前的base case 都很简单, 直接走到底判断一下就行了; 但是这里不一样:

• 一个 PATH 有可能在走到底之前就结束了;
• 如果一个 PATH 提前结束了,不代表就可以直接回头上行了, 还必须继续往下走. 两个结果要加起来;

要学习到的一个经验就是, 要学会考虑search hit( for dfs or backtracking), 不能老是指望走到底 leaf 为止;

最后的速度是31(52), 一般性;

看了 discussion 发现我这里其实可以把 collect 跟 main 写到一起:

public class Solution {  
    public int pathSum(TreeNode root, int sum) {  
        if(root == null)  
            return 0;  
        return findPath(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);  
    }  

    public int findPath(TreeNode root, int sum){  
        int res = 0;  
        if(root == null)  
            return res;  
        if(sum == root.val)  
            res++;  
        res += findPath(root.left, sum - root.val);  
        res += findPath(root.right, sum - root.val);  
        return res;  
    }     
}

Problem Description

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:

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

  10  
 /  \  
5   -3  

/ \ \
3 2 11
/ \ \
3 -2 1

Return 3. The paths that sum to 8 are:

1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
   Difficulty:Easy
   Category:Algorithms
   Acceptance:39.49%
   Contributor: Stomach_ache
   Related Topics
   tree
   Similar Questions
   Path Sum Path Sum II