Path Sum III

这道题明显用O(n^2)的做法是可以做到的，不过貌似有O(n)的算法

class Solution(object):
    result = 0
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        if not root:
            return self.result

        stack = [root]
        while stack:
            node = stack.pop()
            self.count(node, sum)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)

        return self.result

    def count(self, root, target):
        if not root:
            return 
        if not root.left and not root.right:
            self.result = self.result + 1 if root.val == target else self.result
            return 
        self.result = self.result + 1 if root.val == target else self.result
        self.count(root.left, target - root.val)
        self.count(root.right, target - root.val)

O(n)的做法利用的是前缀和与回溯的概念，利用哈希表记录单一路径的累积和，这种方法代码简单，但是逻辑顺序耦合高，一些同层的处理顺序稍微颠倒就会出错

class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        store = collections.Counter()
        store[0] += 1
        result = self.helper(root, 0, sum, store)
        return result

    def helper(self, root, base, sum, store):
        if not root:
            return 0

        base += root.val
        tmp = store.get(base - sum, 0)
        store[base] += 1
        left = self.helper(root.left, base, sum, store)
        right = self.helper(root.right, base, sum , store)
        store[base] -= 1
        return left + right + tmp