/112. Path Sum
Previous|Next

112. Path Sum

Easy
Trees54.5% acceptance

Given the root node of a binary tree (as a TreeNode object) and an integer sum_value, return True if there exists a root-to-leaf path in the tree such that the sum of the node values along the path equals sum_value. A leaf node is defined as a node with no left or right children.

Example 1

Input: root = TreeNode(10, TreeNode(5, TreeNode(2), TreeNode(7)), TreeNode(15, None, TreeNode(20))) sum_value = 22

Output: True

Explanation: Path 10 -> 5 -> 7 sums to 22.

Example 2

Input: root = TreeNode(3, TreeNode(1), TreeNode(4)) sum_value = 8

Output: False

Explanation: No root-to-leaf path sums to 8.

Example 3

Input: root = None sum_value = 0

Output: False

Explanation: Empty tree has no root-to-leaf path.

Constraints

  • The number of nodes in the binary tree is in the range [0, 5000].
  • Each node's value is in the range [-1000, 1000].
  • sum_value is in the range [-1000, 1000].
Python (current runtime)

Case 1

Input: root = TreeNode(-2, None, TreeNode(-3)) sum_value = -5

Expected: True

Case 2

Input: root = TreeNode(1, TreeNode(2), TreeNode(3)) sum_value = 4

Expected: True

Case 3

Input: root = TreeNode(5, TreeNode(4), TreeNode(8, TreeNode(13), TreeNode(4, None, TreeNode(1)))) sum_value = 26

Expected: True

Case 4

Input: root = TreeNode(7) sum_value = 7

Expected: True

Case 5

Input: root = TreeNode(1, TreeNode(2), TreeNode(3)) sum_value = 10

Expected: False