Path Sum III

Problem Id: 437 Difficulty: Medium Tag: Tree


Intuition

In the DFS process, we could keep a stack to save the nodes in the path from root to a current node. And for each node, we could iterate through this stack to find how many paths are there which sum up to the target and ends with the current node.

A small optimization to count how many paths could sum up to the target for each node could be used here.

sum(self.stack[start:]) = self.stack_sum[-1] - self.stack_sum[start - 1]

With this optimization, the time complexity could be reduced to O(n * n).

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def pathSum(self, root: TreeNode, target: int) -> int:
        self.count = 0
        self.stack_sum = [0]
        self._helper(root, target)
        return self.count

    def _helper(self, node, target):
        if node is None:
            return
        self.stack_sum.append(self.stack_sum[-1] + node.val)
        for start in range(0, len(self.stack_sum) - 1):
            if self.stack_sum[-1] - self.stack_sum[start] == target:
                self.count += 1
        self._helper(node.left, target)
        self._helper(node.right, target)
        self.stack_sum.pop()