Adventure Book Gold
In a choose-your-own-adventure book, every page changes your purse: you find 4 gold, or pay a troll 2. At the bottom of most pages you choose between at most two pages to read next. A page with no choices is an ending. You start with 0 gold on the first page, and that page counts too.
A reader wants to know if some ending can be reached holding exactly the number of gold coins a puzzle at the back of the book asks for.
Your task
Write exactGoldEnding(root, target). Each node's value is the gold change on that page. Return true if some path from the root down to a leaf (a node with no children) has values adding up to exactly target. Otherwise return false.
A path must end at a leaf; stopping on a page that still has a choice does not count. An empty book has no endings, so it returns false for every target. Trees are shown in level order, like [3, 4, -2, 6, 1, null, 5], where null marks a missing child. Your function receives real TreeNode objects with val, left and right.
exactGoldEnding(root: TreeNode, target: int) → bool
Examples
root = [3, 4, -2, 6, 1, null, 5] target = 8
true
The three endings give 3 + 4 + 6 = 13, 3 + 4 + 1 = 8 and 3 + (-2) + 5 = 6. The path 3 → 4 → 1 ends with exactly 8 gold.
root = [3, 4, -2, 6, 1, null, 5] target = 7
false
After pages 3 and 4 you hold 7 gold, but page 4 is not an ending: you must keep reading, and both of its choices change your purse. The three endings give 13, 8 and 6, so no ending has exactly 7.
Constraints
- 0 ≤ number of pages ≤ 1,000
- -1,000 ≤ gold change on a page ≤ 1,000
- -1,000,000 ≤ target ≤ 1,000,000
- The tree is at most 500 levels deep.
Start with brute force
Write out every path from the first page to an ending as a list of pages, add up each list, and check if any total equals the target.
It is correct, but it stores whole paths and re-adds the shared beginning of every path. In a long book where most paths share their first few hundred pages, that is a lot of repeated adding. Carrying one running number down the tree means each page is added exactly once.
Hints
0 of 4 shown- Hint 1
Suppose you are on page 4 of the first example holding 7 gold, and the target is 8. What must the rest of your path add up to?
- Hint 2
From any page, the question shrinks: you need
target - (gold so far)from the pages still ahead. That is the same question on a smaller tree. - Hint 3
When do you stop? Think about a page with no choices: when is it a success? And can you stop early when your running total is already above the target?
- Hint 4
Recurse with the remaining amount: at a null return false; at a leaf return whether its value equals what is left; otherwise try both children with
remaining - node.valand return true if either works. Do not cut off a path because the total is too big: later pages can be negative.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Instead of adding up whole paths at the end, carry what is still needed down the tree. Each page subtracts its own value and passes the rest to its children.
Trace [3, 4, -2, 6, 1, null, 5] with target 8:
- Page 3: still need 8 - 3 = 5. Not an ending, so ask both children for 5.
- Page 4: still need 5 - 4 = 1. Not an ending, ask its children for 1.
- Page 6 is an ending: 1 - 6 = -5, not 0, so false.
- Page 1 is an ending: 1 - 1 = 0. True, and the
||(or) stops the search.
The leaf check is what makes the second example false: on page 4 with target 7 the remaining amount is 0, but page 4 has children, so it does not count.
function exactGoldEnding(root, target) {
if (root === null) return false;
const remaining = target - root.val;
if (root.left === null && root.right === null) {
return remaining === 0; // an ending: did we hit it exactly?
}
return exactGoldEnding(root.left, remaining)
|| exactGoldEnding(root.right, remaining);
}def exact_gold_ending(root, target):
if root is None:
return False
remaining = target - root.val
if root.left is None and root.right is None:
return remaining == 0 # an ending: did we hit it exactly?
return (exact_gold_ending(root.left, remaining)
or exact_gold_ending(root.right, remaining))Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.