Path Sum

This is part of my series where I memo learning from Leetcode. If you have better solutions or ideas, please leave a comment!

Problems

Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf >path such that adding up all the values along the path equals the given >sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
11  13  4
 /  \        \
7    2        1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is >22.

We want to know the sum of the value of the route from root to leaf.

In the above example, root is 5 and leaves are 13, 7, 2 and 1, so we have to check the route 5->8->13, 5->4->11->7, 5->4->11->2 and 5->8->4->1.

Approach

We are gonna check the four route by BFS(breadth first search).

In the above example, the BFS order is [5, 4, 8, 11, 13, 4, 7, 2, 1].

We are able to get the sum of the value of the route by adding the value of node to the value of its children. That's say, when the root's value is 5 and the children's values are 4 and 8, we make the children's values are 9 and 13 by adding the root's value and repeat it until the child is a leaf.

Solution

from collections import deque
class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if root is None:
            return False

        queue = deque([root,])

        while queue:
            node = queue.popleft()
            if node.left is not None:
                node.left.val += node.val
                queue.append(node.left)
            if node.right is not None:
                node.right.val += node.val
                queue.append(node.right)
            if node.right is None and node.left is None and node.val == sum:
                return True
        return False 

Thank you for reading this article!
I always welcome your feedback, question, and idea.

Comments

[miniscruff]

It probably won't help much but before you append to the queue you can check if the node.val >= sum and skip the append. Would only apply if our node values where always >= 0 though.

[Shoryu]

That's a very good way to work effectively. Thanks a lot.