Added 2 solutions

varunu28 · varunu28 · commit bddfe38d2281 · 2019-07-02T17:28:16.000-07:00
diff --git a/Hard/Recover a Tree From Preorder Traversal.java b/Hard/Recover a Tree From Preorder Traversal.java
@@ -0,0 +1,44 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public TreeNode recoverFromPreorder(String S) {
+        Map<Integer, TreeNode> map = new HashMap<>();
+        int idx = 0;
+        int n = S.length();
+
+        while (idx < n) {
+            int level = 0;
+            StringBuilder sb = new StringBuilder();
+
+            while (idx < n && S.charAt(idx) == '-') {
+                level++;
+                idx++;
+            }
+
+            while (idx < n && Character.isDigit(S.charAt(idx))) {
+                sb.append(S.charAt(idx++));
+            }
+
+            TreeNode currNode = new TreeNode(Integer.parseInt(sb.toString()));
+            map.put(level, currNode);
+            if (level > 0) {
+                TreeNode parent = map.get(level - 1);
+                if (parent.left == null) {
+                    parent.left = currNode;
+                }
+                else {
+                    parent.right = currNode;
+                }
+            }
+        }
+
+        return map.get(0);
+    }
+}
diff --git a/Medium/Distribute Coins in Binary Tree.java b/Medium/Distribute Coins in Binary Tree.java
@@ -0,0 +1,37 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    int numOfSteps;
+    public int distributeCoins(TreeNode root) {
+        numOfSteps = 0;
+        postorder(root);
+        
+        return numOfSteps;
+    }
+    
+    private int postorder(TreeNode root) {
+        if (root == null) {
+            return 0;
+        }
+        
+        int coin = postorder(root.left) + postorder(root.right);
+        
+        if (root.val == 0) {
+            coin += -1;
+        }
+        else {
+            coin += root.val - 1;
+        }
+        
+        numOfSteps += Math.abs(coin);
+        
+        return coin;
+    }
+}
