Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created January 22, 2019 05:13
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/550b36ea20d4c84924cd757949b7410d to your computer and use it in GitHub Desktop.
Save jianminchen/550b36ea20d4c84924cd757949b7410d to your computer and use it in GitHub Desktop.
979. Distribute Coins in Binary Tree - solution I wrote in the contest on Jan. 19, 2019. The solution is not working
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int DistributeCoins(TreeNode root)
{
var list = new List<int>();
inorderTraversal(root, list);
var length = list.Count;
int coinsMove = 0;
var zeroPositions = new List<int>();
var CoinPositions = new List<int>();
for(int i = 0; i < length; i++)
{
if(list[i] == 0)
{
zeroPositions.Add(i);
}
else if(list[i] > 1)
{
CoinPositions.Add(i);
}
}
int zeroIndex = 0;
int coinIndex = 0;
while(zeroIndex < zeroPositions.Count &&
coinIndex < CoinPositions.Count)
{
var coinPosition = CoinPositions[coinIndex];
var zeroPosition = zeroPositions[zeroIndex];
coinsMove += Math.Abs(coinPosition - zeroPosition);
zeroIndex++;
list[coinPosition]--;
if(list[coinPosition] == 1)
{
coinIndex++;
}
}
return coinsMove;
}
private static void inorderTraversal(TreeNode root, List<int> list)
{
if (root == null)
return;
inorderTraversal(root.left, list);
list.Add(root.val);
inorderTraversal(root.right, list);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment