Added 3 solutions

varunu28 · varunu28 · commit a4f60edb88a4 · 2018-10-19T14:05:26.000-07:00
diff --git a/Easy/Two Sum IV - Input is a BST.java b/Easy/Two Sum IV - Input is a BST.java
@@ -8,15 +8,42 @@
  * }
  */
 class Solution {
-    Set<Integer> set = new HashSet<>();
     public boolean findTarget(TreeNode root, int k) {
-        if (root == null) return false;
-        if (set.contains(k - root.val)) {
-            return true;
+        Stack<TreeNode> stack = new Stack<>();
+        while (root != null) {
+            stack.push(root);
+            root = root.left;
         }
         
-        set.add(root.val);
+        Set<Integer> set = new HashSet<>();
+        int min = popStack(stack);
+        set.add(min);
         
-        return findTarget(root.right, k) || findTarget(root.left, k);
+        while (!stack.isEmpty()) {
+            int num = popStack(stack);
+            if (set.contains(k-num)) {
+                return true;
+            }
+            
+            if (min + num > k) {
+                return false;
+            }
+            
+            set.add(num);
+        }
+        
+        return false;
+    }
+    
+    private int popStack(Stack<TreeNode> stack) {
+        TreeNode n = stack.pop();
+        TreeNode right = n.right;
+        
+        while (right != null) {
+            stack.push(right);
+            right = right.left;
+        }
+        
+        return n.val;
     }
 }
diff --git a/Medium/Binary Tree Vertical Order Traversal.java b/Medium/Binary Tree Vertical Order Traversal.java
@@ -0,0 +1,65 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    Map<Integer, List<Integer>> map = new TreeMap<>();
+    public List<List<Integer>> verticalOrder(TreeNode root) {
+        List<List<Integer>> ans = new ArrayList<>();
+        updateMap(root, 0);
+        
+        for (int key : map.keySet()) {
+            ans.add(map.get(key));
+        }
+        
+        return ans;
+    }
+    
+    private void updateMap(TreeNode root, int level) {
+        if (root == null) {
+            return;
+        }
+        
+        Queue<Element> queue = new LinkedList<>();
+        queue.add(new Element(root, 0));
+        
+        while (!queue.isEmpty()) {
+            int size = queue.size();
+            
+            while (size-- > 0) {
+                Element temp = queue.remove();
+                if (map.containsKey(temp.level)) {
+                    map.get(temp.level).add(temp.node.val);
+                }
+                else {
+                    List<Integer> list = new ArrayList<>();
+                    list.add(temp.node.val);
+                    map.put(temp.level, list);
+                }
+                
+                if (temp.node.left != null) {
+                    queue.add(new Element(temp.node.left, temp.level-1));
+                }
+                
+                if (temp.node.right != null) {
+                    queue.add(new Element(temp.node.right, temp.level+1));
+                }
+            }
+        }
+    }
+}
+
+class Element {
+    public TreeNode node;
+    public int level;
+
+    public Element(TreeNode node, int level) {
+        this.node = node;
+        this.level = level;
+    }
+}
diff --git a/Medium/Maximum Binary Tree.java b/Medium/Maximum Binary Tree.java
@@ -9,29 +9,29 @@
  */
 class Solution {
     public TreeNode constructMaximumBinaryTree(int[] nums) {
-        if (nums == null) return null;
-        return constructMaximumBinaryTreeImpl(nums,0,nums.length-1);
+        if (nums.length == 0) {
+            return null;
+        }
+        
+        return constructTree(nums, 0, nums.length-1);
     }
     
-    public TreeNode constructMaximumBinaryTreeImpl(int[] nums, int start, int end) {
-        
+    private TreeNode constructTree(int[] nums, int start, int end) {
         if (start > end) {
             return null;
         }
         
         int idx = start;
-        
-        for (int i = start + 1; i <= end; i++) {
+        for (int i=start+1; i<=end; i++) {
             if (nums[i] > nums[idx]) {
                 idx = i;
             }
         }
         
         TreeNode root = new TreeNode(nums[idx]);
         
-        root.left = constructMaximumBinaryTreeImpl(nums, start, idx-1);
-        
-        root.right = constructMaximumBinaryTreeImpl(nums, idx+1, end);
+        root.left = constructTree(nums, start, idx-1);
+        root.right = constructTree(nums, idx+1, end);
         
         return root;
     }
