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.
1class TreeNode {
2 int val;
3 TreeNode left, right;
4 TreeNode(int x) { val = x; }
5}
6
7class Solution {
8 private int moves = 0;
9
10 public int distributeCoins(TreeNode root) {
11 dfs(root);
12 return moves;
13 }
14
15 private int dfs(TreeNode node) {
16 if (node == null) return 0;
17 int leftExcess = dfs(node.left);
18 int rightExcess = dfs(node.right);
19 moves += Math.abs(leftExcess) + Math.abs(rightExcess);
20 return node.val + leftExcess + rightExcess - 1;
21 }
22}This Java solution performs a similar post-order traversal, using a helper method dfs to calculate excess coins and accumulate the necessary moves. It updates and returns the moves from a private variable.