437. 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:

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

方法1: recursion

思路：

如果沿用之前的方法，首先我们只考虑必须从根节点开始成链的情况。那么需要做的和一般dfs没有什么区别，如果沿途遇到了root->val和累计target相等的情况，直接将当前结果送回，并计数。那么如果算进不从根节点开始的情况？

如果沿途同时揭露了path，这时候只需要从起始节点开始尝试一个个删除，判断删除一个个头节点后能否再次出现满足条件的结果，有就送回并计数。

Complexity

Time complexity: O(n^2)
Space complexity: O(n)

class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        int result = 0; int curSum = 0;
        vector<int> current;
        pathHelper(root, sum, curSum, result, current);
        return result;
    }
    
    void pathHelper(TreeNode* root, int sum, int & curSum, int &result, vector<int> & current){
        if (!root) return;
        // 必须包含根节点的路径是否满足
        curSum += root -> val;
        current.push_back(root -> val);
        if (curSum == sum)  result++;
        
        // 去掉前面的头节点的路径中是否有满足条件的
        int t = curSum;
        for (int i = 0; i < current.size() - 1; i++){
            t -= current[i];
            if (t == sum) result ++;
        }
        
        pathHelper(root -> left, sum, curSum, result, current);
        pathHelper(root -> right, sum, curSum, result, current);
        // 因为都使用了引用，要负责清洁
        curSum -= root -> val;
        current.pop_back();
        return;
    }
};

方法2:

grandyang: http://www.cnblogs.com/grandyang/p/6007336.html
思路：

这种做法就很精妙了。拆成了两个递归函数，一个用来统计必须包含当前根节点的解，并细分成根节点及以上解，与根节点连接以上与以下构成的解，另一个用来跳过当前根节点。

SumUp:

1. 返回结果的第一部分cur == sum ：根节点及以上prev相加能否满足？
2. 返回结果的第二部分SumUp(root -> left, cur, sum) ：根节点能否连接以上和左子树的解？
3. 返回结果的第三部分SumUp(root -> right, cur, sum) ：根节点能否连接以上和右子树的解？

PathSum:
4. 返回结果的第一部分SumUp(root, cur, sum): 包含根节点的解
5. 返回结果的第二部分PathSum(root -> left, cur, sum): 左子树解
6. 返回结果的第二部分PathSum(root -> left, cur, sum): 右子树解

Complexity

Time complexity: O(n^2)
Space complexity: O(n)

class Solution4 {
public:
    int pathSum(TreeNode* root, int sum) {
        if (!root) return 0;
        return sumUp(root, 0, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
    }
    int sumUp(TreeNode* node, int pre, int& sum) {
        if (!node) return 0;
        int cur = pre + node->val;
        return (cur == sum) + sumUp(node->left, cur, sum) + sumUp(node->right, cur, sum);
    }
};

方法3: 双重递归（复杂度比较高）

公瑾：https://www.youtube.com/watch?v=AqfSV2B_TMY

// 方法1: 非最优解，双重递归
// not working, 会产生多余解，unconnected trees
// 
// class SolutionBruteForce(object):
//     def find_paths(self, root, target):
//         if root:
//             return int(root.val == target) + self.find_paths(root.left, target-root.val) + self.find_paths(root.right, target-root.val)
//         return 0

//     def pathSum(self, root, sum):
//         """
//         :type root: TreeNode
//         :type sum: int
//         :rtype: int
//         """
//         if root:
//             return self.find_paths(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)
//         return 0