Distribute Coins in Binary Tree LeetCode solution in C++

1
class Solution {
2
 public:
3
  // calculate required moves in postorder manner
4
  int traverse(TreeNode *root, int &moves) {
5
    if (!root) return 0;
6

7
    // left subtree excess amount coin
8
    int left = traverse(root->left, moves);
9

10
    // right subtree excess amount coin
11
    int right = traverse(root->right, moves);
12

13
    // moves needed to neutralize the excess amount of coins of left and right
14
    // subtree
15
    moves += abs(left) + abs(right);
16

17
    // current subtree including current root excess amount is
18
    // total coins in the subtree - total nodes in the subtree
19
    // left and right subtree excess amount coin + root coin -1
20
    return root->val + left + right - 1;
21
  }
22

23
  int distributeCoins(TreeNode *root) {
24
    int moves = 0;
25
    traverse(root, moves);
26
    return moves;
27
  }
28
};