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.
1#include <cstdlib>
2
3struct TreeNode {
4 int val;
5 TreeNode *left;
6 TreeNode *right;
7 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8};
9
10class Solution {
11 int moves = 0;
12public:
13 int distributeCoins(TreeNode* root) {
14 dfs(root);
15 return moves;
16 }
17
18 int dfs(TreeNode* node) {
19 if (!node) return 0;
20 int leftExcess = dfs(node->left);
21 int rightExcess = dfs(node->right);
22 moves += abs(leftExcess) + abs(rightExcess);
23 return node->val + leftExcess + rightExcess - 1;
24 }
25};This C++ solution uses a standard DFS approach in post-order fashion, counting the moves for handling excess coins at each step. The recursive method returns the balance status at each node.