A good way into this one is to ask: what do we need to remember so we never redo work blindly? For 979. Distribute Coins in Binary Tree, the solution in this repository is mainly a two pointers solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: two pointers.
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are dfs, distributeCoins.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(N)O(N), where NN is the number of nodes in the tree.
- Space: O(H)O(H), where HH is the height of the tree.
Guide
C++ Solution
Your submission
The accepted solution
01/**
02Given the root of a binary tree with N nodes, each node in the tree has node.val coins, and there are N coins total.
03
04In one move, we may choose two adjacent nodes and move one coin from one node to another. (The move may be from parent to child, or from child to parent.)
05
06Return the number of moves required to make every node have exactly one coin.
07**/
08
09/**
10Approach 1: Depth First Search
11Intuition
12
13If the leaf of a tree has 0 coins (an excess of -1 from what it needs),
14then we should push a coin from its parent onto the leaf.
15If it has say, 4 coins (an excess of 3),
16then we should push 3 coins off the leaf. In total,
17the number of moves from that leaf to or from its parent is excess = Math.abs(num_coins - 1).
18Afterwards, we never have to consider this leaf again in the rest of our calculation.
19
20Algorithm
21
22We can use the above fact to build our answer.
23Let dfs(node) be the excess number of coins in the subtree at or below this node: namely,
24the number of coins in the subtree, minus the number of nodes in the subtree.
25Then, the number of moves we make from this node to and from its children is
26abs(dfs(node.left)) + abs(dfs(node.right)).
27After, we have an excess of node.val + dfs(node.left) + dfs(node.right) - 1 coins at this node.
28**/
29
30/**
31Complexity Analysis
32
33Time Complexity: O(N)O(N), where NN is the number of nodes in the tree.
34
35Space Complexity: O(H)O(H), where HH is the height of the tree.
36**/
37
38//Runtime: 12 ms, faster than 98.50% of C++ online submissions for Distribute Coins in Binary Tree.
39//Memory Usage: 14 MB, less than 49.12% of C++ online submissions for Distribute Coins in Binary Tree.
40/**
41 * Definition for a binary tree node.
42 * struct TreeNode {
43 * int val;
44 * TreeNode *left;
45 * TreeNode *right;
46 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
47 * };
48 */
49class Solution {
50public:
51 int moves = 0;
52
53 int dfs(TreeNode* node){
54 if(node==NULL) return 0;
55 int L = dfs(node->left), R = dfs(node->right);
56 //the moves needed to make this subtree have adequate amount of coins
57 //add abs() because we don't care the direction(in or out)
58 //not consider the move on root since it's thought as a relay point
59 moves += (abs(L) + abs(R));
60 //number of coins needed to be moved out this subtree
61 return node->val - 1 + (L + R);
62 }
63
64 int distributeCoins(TreeNode* root) {
65 dfs(root);
66 return moves;
67 }
68};Cost