TreeNode(val, left=None, right=None) is in the starter. Keep it.
Every node of a binary tree holds an integer between -10**6 and 10**6 (possibly negative), so a path's cost can exceed the 32-bit range. A leaf is a node with no children, and a root-to-leaf path starts at the root and walks down, one child at a time, until it reaches a leaf. Its cost is the sum of the values on it, both ends included.
Write cheapest_path(root: TreeNode | None) -> list[int] that returns the values along the root-to-leaf path of smallest cost, from the root down to the leaf.
- If several paths tie for the smallest cost, return the leftmost one: the one whose leaf comes first when the tree's leaves are listed left to right.
- A node with one child is not a leaf; a path must continue through that child.
- An empty tree (
root is None) gives[].
# 5
# / \
# 4 -2
# / \ \
# -8 1 3
# / \
# -9 6
cheapest_path(root) # [5, -2, 3, -9] cost -3, beating 5 + 4 - 8 = 1
# 1
# / \
# 2 2
cheapest_path(root) # [1, 2] both paths cost 3; the left one wins
Trees can have up to 2 * 10**5 nodes and be up to 3 * 10**4 levels deep, so either raise the recursion limit with sys.setrecursionlimit or walk the tree with your own stack. Aim for O(n): copying the current path at every node or every leaf is quadratic on a long spine.
Show hint
You only need to build one path, the winner's. Keep enough information while walking to rebuild it once at the end.