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.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 private int moves = 0;
10
11 public int DistributeCoins(TreeNode root) {
12 Dfs(root);
13 return moves;
14 }
15
16 private int Dfs(TreeNode node) {
17 if (node == null) return 0;
18 int leftExcess = Dfs(node.left);
19 int rightExcess = Dfs(node.right);
20 moves += Math.Abs(leftExcess) + Math.Abs(rightExcess);
21 return node.val + leftExcess + rightExcess - 1;
22 }
23}This C# code follows the similar DFS approach to calculate and accumulate moves necessary for balancing coins. It uses attributes to store and return the number of moves globally.