Leetcode 112. Path Sum (Python)

Related Topic

Depth-First-Search. Tree.

Description

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.

Sample I/O

Example 1

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.

Note

A leaf is a node with no children.

Methodology

This question can be solved by Depth First Search.

We use dfs to traversal the tree. Each time we compare the sum and the current root value if they are same and the root does not have left child and right child (root is leaf), then we find a path that equal to give sum. Otherwist, we make the sum equal to sum - root.val and continue recursively find the next root.

Code(DFS)

def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if root is None: return False
        if root.left is None and root.right is None and sum == root.val:
            return True
        return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)

BigO

We traversal all nodes of the tree at most once so total time complexity is O(n)