Introduction
It is the algorithm of weekly contest 120. I wrote one solution in the contest but it does not work. I took some time to learn and write a solution based on the discuss shared by my favorite player.
My practice
Here is my submission.
I wrote a solution in the contest but it does not work. Here is the gist.
I learn the tip in the following:
We traverse children first (post-order traversal), and return the balance 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 balance: -3 (left) + 1 (right) - 1 (keep one coin for the root) + r->val (coins in the root).
The above image is the copy from the leetcode discuss.
I learn the tip in the following:
We traverse children first (post-order traversal), and return the balance 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 balance: -3 (left) + 1 (right) - 1 (keep one coin for the root) + r->val (coins in the root).
The above image is the copy from the leetcode discuss.
No comments:
Post a Comment