I am reading the solution of this problem
solution
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); <----- do not understand
return r->val + left + right - 1;
}
int distributeCoins(TreeNode* r, int moves = 0) {
traverse(r, moves);
return moves;
}
I have hard time to understand that
- why move = move + abs(left) + abs(right) in current subtree?
- why we don’t involve curr_node? e.g move = move + abs(curr_node) + abs(left) + abs(right)?
- does it mean in each sub tree the move abs(left) + abs(right) equal moves of left subtree and right subtree only?
- in the top root subtree, move = abs(left) + abs(right), so there is no move for the root node? Looks like abs(left) OR abs(right) cover the move of root node?