437.Path Sum III

Tags: [tree], [stack], [binary_tree]

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

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

Solution: recursion

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

        path_counter = 0
        stack = [root]
        while stack:
            curr = stack.pop()
            path_counter += self.counting_path(curr, sum, 0)

            if curr.right:
                stack.append(curr.right)
            if curr.left:
                stack.append(curr.left)

        return path_counter

    def counting_path(self, root, sum, tmp_sum):
        # base case
        if not root:
            return 0

        counter = 0
        tmp_sum += root.val
        if tmp_sum == sum:
            counter += 1

        return counter + self.counting_path(root.left, sum, tmp_sum) +\
                         self.counting_path(root.right, sum, tmp_sum)

Revelation:

• Because the path can start at any node and end at any node, so when we meet the tmp_sum == sum, we cannot stop, because there exists this scenario: [5] -> [3] -> [-3] -> [3], which contains two paths.

Note:

• Time complexity = O(n^2), n is the number of nodes in the given tree.
• We can use iteration or recursion to iterate all nodes in the tree, here we choose to use iteration.
• If we use iteration to generate the preorder traversal, we should do stack.append(curr.right) then do stack.append(curr.left).