Sponsored
Sponsored
To solve the problem, we perform a post-order traversal of the tree. During this traversal, for each node, we calculate the excess coins (i.e., the number of coins - 1) that need to be moved either up to the parent or down to the children. We accumulate the absolute values of excess coins for each move.
Time Complexity: O(n), where n is the number of nodes in the tree. We visit each node exactly once.
Space Complexity: O(h), where h is the height of the tree due to the recursion stack.
1function TreeNode(val, left, right) {
2 this.val = (val===undefined ? 0 : val);
3 this.left = (left===undefined ? null : left);
4 this.right = (right===undefined ? null : right);
5}
6
7var distributeCoins = function(root) {
8 let moves = 0;
9
10 function dfs(node) {
11 if (!node) return 0;
12 let leftExcess = dfs(node.left);
13 let rightExcess = dfs(node.right);
14 moves += Math.abs(leftExcess) + Math.abs(rightExcess);
15 return node.val + leftExcess + rightExcess - 1;
16 }
17
18 dfs(root);
19 return moves;
20};This JavaScript solution executes a DFS in post-order, similar to other implementations. It calculates the number of moves needed to balance coins at each node by adjusting the accumulated moves and handling the excess coins down from children or up to parents as needed.