Problem statement
Intuition
- brute_force approach will be to calculate sum of all path and select the greatest.
- Heredepth_first_search of tree will help.
- Calculate root val + maxLeftVal + maxRightPath
- return max(leftMaxPath + rightMaxPath) + val
- time_complexity O(n)
- DFS- Tree
- Tree DFS Algorithm
- Tree
- We will be usingpreorder_traversal since it is the only one which starts with root and here we need to find sum between root and target.
- Q. Canpostorder_traversal be considered here as well? Don’t think so since it will help only in case left to root is max Path else it will not give the right answer.
pseudo_code
#Linked_Representation or #array_representation ?
t = 3 has 1 and 2, 1 has 5 and 7, 2 has null
Target = 7
FindPathSum(root, target):
if root == null:
Code
class Solution(object):
def hasPathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
"""
if not root:
return False
elif not root.left and not root.right:
if root.val == sum:
return True
else:
return False
return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)What intuition do above program implement?
- if the node is null return false to exit program
- if both left and right node are null then in thisparameterized_recursion check if sum variable is equal to root, from previous step we know root is not null, of root vale is equal to sum that means it has the path sum, so return true else false
- Now since this ispreorder_traversal traverse left then right node substracting root ball from sum, it is alsomultiple_recursion_call , add or condition since of at any of the places sum exists then true has to be returned.