/112. Path Sum
Previous|Next

112. Path Sum

Easy
Trees54.5% acceptance

Given the root node of a binary tree and an integer sum_target, 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_target. A leaf node is defined as a node with no children.

Example 1

Input: root = TreeNode(10, TreeNode(5), TreeNode(15, None, TreeNode(20))) sum_target = 45

Output: False

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

Example 2

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

Output: True

Explanation: Path -2 -> -3 sums to -5.

Example 3

Input: root = None sum_target = 7

Output: False

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

Constraints

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

Case 1

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

Expected: True

Case 2

Input: root = TreeNode(7, TreeNode(3, None, TreeNode(2)), TreeNode(5)) sum_target = 12

Expected: False

Case 3

Input: root = TreeNode(0, TreeNode(-1), TreeNode(1)) sum_target = 0

Expected: True