This is part of my series where I memo learning from Leetcode. If you have better solutions or ideas, please leave a comment!
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.
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
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.
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.