Path Sum III

Path Sum III

update Jun 27, 2017

leetcode

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

解释下：这道题的意思就是说找任意path上相邻节点的和是 given sum value 的数量。 思路： 这道题目的难点是要考虑从上到下每一段path上nodes的和。我们可以写两个 recursive function， 外层的用来对每个node（做为root）考虑其子树中的所有path。而内层 function 则用来考虑包含该 node（做为root）的所有path。 细节： 对于内层function，每次调用下一层时候，传入下层的 sum 变为 sum - node.val，这样当下层 val == sum 的时候，就说明有了一条满足条件的path。

Python Code：

    # python 2.7
    class Solution(object):
        def pathSum(self, root, sum):
            """
            :type root: TreeNode
            :type sum: int
            :rtype: int
            """
            if not root:
                return 0
            return self.dfs(root, sum) +
                   self.pathSum(root.left, sum) +
                   self.pathSum(root.right, sum)

        def dfs(self, node, target):
            if not node:
                return 0
            return (node.val == target) +
                   self.dfs(node.left, target - node.val) +
                   self.dfs(node.right, target - node.val)

Java code:

    // java
    class Solution {
        public int pathSum(TreeNode root, int sum) {
            if (root == null) return 0;
            return helper(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
        }
        // 返回以当前node开始向下的符合条件的path数量
        private int helper(TreeNode root, int target) {
            if (root == null) return 0;
            if (root.val == target) return 1 + helper(root.left, 0) + helper(root.right, 0);
            else return helper(root.left, target - root.val) + helper(root.right, target - root.val);
        }
    }

update Jan 27,2018 19:58

Update PreSum 数组 解法

还是利用 dfs，逐层向下构建当前path，不同的是path中存储的是之前每个node.val组成的数组的preSum数组，如此一来每层我们都可以用 O(path.size) 的时间查看目前为止有多少以该节点为终点的路径其 sum 为给定值，优化了时间复杂度。

时间复杂度: 时间应该为 O(NlogN) 因为每次需要 O(当前depth) 的时间来遍历presum数组，而depth最高为 logN ，一共有 N 个节点，所以上界应该为 O(NlogN); 空间复杂度为 O(height);

• Java Code:

    class Solution {
        public int pathSum(TreeNode root, int sum) {
            List<Integer> preSum = new ArrayList<>();
            preSum.add(0);
            return helper(root, preSum, sum);
        }
  
        private int helper(TreeNode root, List<Integer> preSum, int sum) {
            if (root == null) return 0;
            int ret = 0;
            preSum.add(preSum.get(preSum.size() - 1) + root.val);
            for (int i = 0; i < preSum.size() - 1; ++i) {
                if (preSum.get(preSum.size() - 1) - preSum.get(i) == sum) {
                    ret++;
                }
            }
            int left = helper(root.left, preSum, sum);
            int right = helper(root.right, preSum, sum);
            preSum.remove(preSum.size() - 1);
            return ret + left + right;
        }
    }

• C++ Code:

    class Solution {
        int helper(TreeNode* root, vector<int>& path, int sum) {
            if (root == nullptr) return 0;
            path.push_back(path.back() + root->val);
            int ret = 0;
            for (int i = 0; i < path.size() - 1; ++i) { // 注意这里，避免相同节点相减出现sum==0的假象
                if (path.back() - path[i] == sum) {
                    ret++;
                }
            }
            int left = helper(root->left, path, sum);
            int right = helper(root->right, path, sum);
            path.pop_back();
            return left + right + ret;
        }
    public:
        int pathSum(TreeNode* root, int sum) {
            vector<int> path{0};
            return helper(root, path, sum);
        }
    };

update 2018-06-29 20:31:55

Update: 使用 prefix sum + HashMap，最快解法

最初的解法是维持一个path，每到一个新的node，就向上遍历path，看有无 sum==target 的情况，这种做法的时间复杂度为 O(N*(logN^2))。

进一步优化，把path改成 prefix sum array，这样时间复杂度就变为了 O(NlogN)。

接下来，我们可以继续优化，使用 HashMap 来存储 prefix sums，即在 map 中存当前path中的 prefix sums 以及其个数，每次到了新node，向上query的时间变为 O(1)，总时间复杂度降为 O(N);

class Solution {
    private int ret = 0;
    public int pathSum(TreeNode root, int sum) {
        Map<Integer, Integer> path = new HashMap<>();
        path.put(0, 1);
        dfs(root, path, 0, sum);
        return ret;
    }
    private void dfs(TreeNode root, Map<Integer, Integer> path, int lastSum, int sum) {
        if (root == null) return;
        int currSum = lastSum + root.val;
        ret += path.getOrDefault(currSum - sum, 0);
        path.put(currSum, path.getOrDefault(currSum, 0) + 1);
        dfs(root.left, path, currSum, sum);
        dfs(root.right, path, currSum, sum);
        path.put(currSum, path.get(currSum) - 1);
    }
}