[LeetCode] #112: Path Sum

Kyu Hwan Choi·2022년 5월 4일
0

LeetCode

목록 보기
7/11
post-thumbnail

Problem:

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.


Process:

Objective: Find if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

Constraints:
1. The number of nodes in the tree is in the range [0, 5000].
2. -1000 <= Node.val <= 1000
3. -1000 <= targetSum <= 1000

Edge Cases:
1. Empty Tree
2. Tree Nodes w/ only positive values
3. Tree Nodes w/ only negative values
4. Tree Nodes w/ mixed positive and negative values
*I tried to reduce time by not adding to child once the sum of values has exceeded target value. However, if there is a mixed positive and negative values, you cannot use this criteria to judge whether you should try out that path.


Solution:

Attempt #1: (Iteration) Check if node is leaf and if target value is reached

  • Time Complexity: O(n), where n is the number of TreeNodes
  • Space Complexity: O(n)

How it works:
1. Check if the current node is a leaf and if target value is reached. If so, short circuit and return True
2. Add node.left and node.right to the stack of nodes_to_visit. (The values in their node tuple will be the sum of values to reach that node + the value of node)

def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        node_tuple = None
        
        # When the Tree is empty
        if root:
            node_tuple = (root, root.val)
            
        nodes_to_visit = []
        
        while node_tuple:
            node, val = node_tuple
            is_leaf = not node.left and not node.right
            
            # If the node is leaf and the pathsum equals the target sum
            if is_leaf and val == targetSum:
                return True
            
            # Adding left and right child node to nodes_to_visit stack
            if node.left:
                nodes_to_visit.append((node.left, val + node.left.val))
            if node.right:
                nodes_to_visit.append((node.right, val + node.right.val))
            
            # Checking if we've traversed through the whole tree
            if nodes_to_visit:
                node_tuple = nodes_to_visit.pop()
            else:
                node_tuple = None
        
        return False

LeetCode Question #112

0개의 댓글