437. Path Sum III

https://leetcode.com/problems/path-sum-iii/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.

Thoughts

先用分治思想，path所在分为三种情况: path初始点在左子树，右子树或从当前结点初始。 trick在从当前结点初始时相当于又是一个分治思想，是求对node.left/right的sum-node.val。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int count = 0;
    private int findPaths(TreeNode node, int sum) {
        if (node == null) {
            return 0;
        }

        int res = 0;
        if (node.val == sum) {
            res++;
        }

        res += findPaths(node.left, sum - node.val);
        res += findPaths(node.right, sum - node.val);

        return res;
    }


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

        return findPaths(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
}

Analysis

两重分治，内外分别都是对树遍历, 时间复杂度O(n^2)。

Ver.2

https://leetcode.com/problems/path-sum-iii/discuss/91878/

preSum思想, 把树看作多条path的array. 利用hash map存储当前path的presum，存在则意味着presum[psum - cur] != null。多个path之间不能弄混了，所以当backtracking结束后要把该结点从path中移除，同时把preSum中相应的sum的频率减一.。注意preSum需要初始化0，用来cover root到当前点的sum刚好等于target的情况。

public int pathSum(TreeNode root, int sum) {
        HashMap<Integer, Integer> preSum = new HashMap();
        preSum.put(0,1);
        return helper(root, 0, sum, preSum);
    }

    public int helper(TreeNode root, int currSum, int target, HashMap<Integer, Integer> preSum) {
        if (root == null) {
            return 0;
        }

        currSum += root.val;
        int res = preSum.getOrDefault(currSum - target, 0);
        preSum.put(currSum, preSum.getOrDefault(currSum, 0) + 1);

        res += helper(root.left, currSum, target, preSum) + helper(root.right, currSum, target, preSum);
        preSum.put(currSum, preSum.get(currSum) - 1);
        return res;
    }

Ver.3

改写成iterative需要注意++presum不能在计算target sum是否存在的前面，因为当target == 0时，我们相当于在问是否存在到cur和为psum的路径，那肯定是存在的。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        if (root == NULL) return 0;
        stack<TreeNode*> s;
        int psum = 0;
        unordered_map<int, int> presum;
        presum[0] = 1;
        int res = 0;
        const auto push_left = [&](TreeNode *cur) {
            while (cur != NULL) {
                s.push(cur);
                psum += cur->val;
                cur = cur->left;
                // The order of the following two lines are important!
                if (presum.find(psum - sum) != presum.end()) res += presum[psum - sum]; 
                ++presum[psum];
            }
        };
        push_left(root);
        TreeNode *pre;
        while (!s.empty()) {
            const auto cur = s.top();
            if (cur->right != NULL && cur->right != pre) {
                push_left(cur->right);
                continue;
            }
            s.pop();
            pre = cur;
            --presum[psum];
            psum -= cur->val;
        }
        return res;
    }
};