Leetcode algorithm study: 979. Distribute Coins in Binary Tree

 March 20, 2022

Here is the link. 

C++ with picture, post-order traversal

votrubac48205

January 19, 2019 8:03 PM

20.8K VIEWS

We traverse childs first (post-order traversal), and return the ballance of coins. For example, if we get '+3' from the left child, that means that the left subtree has 3 extra coins to move out. If we get '-1' from the right child, we need to move 1 coin in. So, we increase the number of moves by 4 (3 moves out left + 1 moves in right). We then return the final ballance: r->val (coins in the root) + 3 (left) + (-1) (right) - 1 (keep one coin for the root).

int traverse(TreeNode* r, int &moves) {
  if (r == nullptr) return 0;
  int left = traverse(r->left, moves), right = traverse(r->right, moves);
  moves += abs(left) + abs(right);
  return r->val + left + right - 1;
}
int distributeCoins(TreeNode* r, int moves = 0) {
  traverse(r, moves);
  return moves;
}

If we can modify values of tree nodes, we can store the balance in nodes, and use the return value to accumulate the number of moves. This way we can get rid of the helper method. The solution below is courtesy of Lee:

int distributeCoins(TreeNode* r, TreeNode* p = nullptr) {
  if (r == nullptr) return 0;
  int res = distributeCoins(r->left, r) + distributeCoins(r->right, r);
  if (p != nullptr) p->val += r->val - 1;
  return res + abs(r->val - 1);
}