aboutsummaryrefslogtreecommitdiff
path: root/distribute_coins_binary_tree.c
diff options
context:
space:
mode:
Diffstat (limited to 'distribute_coins_binary_tree.c')
-rw-r--r--distribute_coins_binary_tree.c30
1 files changed, 30 insertions, 0 deletions
diff --git a/distribute_coins_binary_tree.c b/distribute_coins_binary_tree.c
new file mode 100644
index 0000000..9df6b16
--- /dev/null
+++ b/distribute_coins_binary_tree.c
@@ -0,0 +1,30 @@
+// 979. Distribute Coins in Binay Tree
+#include "leetcode.h"
+
+/*
+ * given the 'root' of a binary tree with 'n' nodes where each 'node' is the
+ * tree that has 'node.val' coins. there are 'n' coins in total throughout the
+ * whole tree. in one move, we may choose two adjacent nodes and move one coin
+ * from one node to another. a move may be from parent to child, or from child
+ * to parent. return the minimum number of moves required to make every node
+ * have exactly one coin.
+ */
+
+struct TreeNode {
+ int val;
+ struct TreeNode *left;
+ struct TreeNode *right;
+};
+
+int dfs(struct TreeNode *root, int steps) {
+ if (!root)
+ return 0;
+ int val = root->val + dfs(root->left, steps) + dfs(root->right, steps);
+ steps += abs(val - 1);
+ return val - 1;
+}
+
+int distributeCoins(struct TreeNode *root) {
+ int steps = 0, tmp = dfs(root, steps);
+ return steps;
+}