Created
January 22, 2019 05:13
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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