Added 5 solutions

varunu28 · varunu28 · commit 699bd2e427e1 · 2018-10-05T09:01:02.000-07:00
diff --git a/Easy/Closest Binary Search Tree Value.java b/Easy/Closest Binary Search Tree Value.java
@@ -0,0 +1,36 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    int ans = 0;
+    double minDiff = Double.MAX_VALUE;
+    
+    public int closestValue(TreeNode root, double target) {
+        updateVal(root, target);    
+        return ans;
+    }
+    
+    private void updateVal(TreeNode root, double target) {
+        if (root == null) {
+            return;
+        }
+        
+        if (Math.abs(root.val - target) < minDiff) {
+            minDiff = Math.abs(root.val - target);
+            ans = root.val;
+        }
+        
+        if (root.val < target) {
+            updateVal(root.right, target);
+        }
+        else {
+            updateVal(root.left, target);
+        }
+    }
+}
diff --git a/Easy/Nested List Weight Sum.java b/Easy/Nested List Weight Sum.java
@@ -0,0 +1,50 @@
+/**
+ * // This is the interface that allows for creating nested lists.
+ * // You should not implement it, or speculate about its implementation
+ * public interface NestedInteger {
+ *     // Constructor initializes an empty nested list.
+ *     public NestedInteger();
+ *
+ *     // Constructor initializes a single integer.
+ *     public NestedInteger(int value);
+ *
+ *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
+ *     public boolean isInteger();
+ *
+ *     // @return the single integer that this NestedInteger holds, if it holds a single integer
+ *     // Return null if this NestedInteger holds a nested list
+ *     public Integer getInteger();
+ *
+ *     // Set this NestedInteger to hold a single integer.
+ *     public void setInteger(int value);
+ *
+ *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
+ *     public void add(NestedInteger ni);
+ *
+ *     // @return the nested list that this NestedInteger holds, if it holds a nested list
+ *     // Return null if this NestedInteger holds a single integer
+ *     public List<NestedInteger> getList();
+ * }
+ */
+class Solution {
+    int sum = 0;
+    
+    public int depthSum(List<NestedInteger> nestedList) {
+        for (NestedInteger n : nestedList) {
+            dfsHelper(n, 1);
+        }    
+        
+        return sum;
+    }
+    
+    private void dfsHelper(NestedInteger n, int depth) {
+        if (n.isInteger()) {
+            sum += n.getInteger() * depth;
+        }
+        else {
+            for (NestedInteger i : n.getList()) {
+                dfsHelper(i, depth+1);
+            }
+        }
+    }
+}
diff --git a/Medium/Find Leaves of Binary Tree.java b/Medium/Find Leaves of Binary Tree.java
@@ -0,0 +1,61 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public List<List<Integer>> findLeaves(TreeNode root) {
+        List<List<Integer>> list = new ArrayList<>();
+        
+        while (root != null) {
+            List<Integer> leaves = getLeaves(root);
+            root = removeLeaves(root);
+            list.add(leaves);
+        }
+        
+        return list;
+    }
+    
+    private TreeNode removeLeaves(TreeNode root) {
+        if (root == null) {
+            return null;
+        }
+        
+        if (root.left == null && root.right == null) {
+            return null;
+        }
+        
+        root.left = removeLeaves(root.left);
+        root.right = removeLeaves(root.right);
+        
+        return root;
+    }
+    
+    private List<Integer> getLeaves(TreeNode root) {
+        Queue<TreeNode> queue = new LinkedList<>();
+        queue.add(root);
+        List<Integer> list = new ArrayList<>();
+        
+        while (!queue.isEmpty()) {
+            TreeNode node = queue.remove();
+            if (node.left == null && node.right == null) {
+                list.add(node.val);
+            }
+            else {
+                if (node.left != null) {
+                    queue.add(node.left);
+                }
+                
+                if (node.right != null) {
+                    queue.add(node.right);
+                }
+            }
+        }
+        
+        return list;
+    } 
+}
diff --git a/Medium/Inorder Successor in BST.java b/Medium/Inorder Successor in BST.java
@@ -0,0 +1,42 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
+        if (p.right != null) {
+            TreeNode node = p.right;
+            while (node.left != null) {
+                node = node.left;
+            }
+            
+            return node;
+        }
+        
+        return getLastLeft(root, p);
+    }
+
+    private TreeNode getLastLeft(TreeNode root, TreeNode p) {
+        TreeNode lastLeft = null;
+        
+        while (root != null) {
+            if (root == p) {
+                break;
+            }
+            else if (root.val < p.val) {
+                root = root.right;
+            }
+            else {
+                lastLeft = root;
+                root = root.left;
+            }
+        }
+        
+        return lastLeft;
+    }
+}
diff --git a/Medium/Nested List Weight Sum II.java b/Medium/Nested List Weight Sum II.java
@@ -0,0 +1,65 @@
+/**
+ * // This is the interface that allows for creating nested lists.
+ * // You should not implement it, or speculate about its implementation
+ * public interface NestedInteger {
+ *     // Constructor initializes an empty nested list.
+ *     public NestedInteger();
+ *
+ *     // Constructor initializes a single integer.
+ *     public NestedInteger(int value);
+ *
+ *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
+ *     public boolean isInteger();
+ *
+ *     // @return the single integer that this NestedInteger holds, if it holds a single integer
+ *     // Return null if this NestedInteger holds a nested list
+ *     public Integer getInteger();
+ *
+ *     // Set this NestedInteger to hold a single integer.
+ *     public void setInteger(int value);
+ *
+ *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
+ *     public void add(NestedInteger ni);
+ *
+ *     // @return the nested list that this NestedInteger holds, if it holds a nested list
+ *     // Return null if this NestedInteger holds a single integer
+ *     public List<NestedInteger> getList();
+ * }
+ */
+class Solution {
+    int maxDepth = 1;
+    int sum = 0;
+    public int depthSumInverse(List<NestedInteger> nestedList) {
+        for (NestedInteger n : nestedList) {
+            updateMaxDepth(n, 1);
+        }
+        
+        for (NestedInteger n : nestedList) {
+            dfsHelper(n, maxDepth);
+        }
+        
+        return sum;
+    }
+    
+    private void dfsHelper(NestedInteger n, int depth) {
+        if (n.isInteger()) {
+            sum += n.getInteger() * depth;
+        }
+        else {
+            for (NestedInteger i : n.getList()) {
+                dfsHelper(i, depth-1);
+            }
+        }
+    }
+    
+    private void updateMaxDepth(NestedInteger n, int depth) {
+        if (n.isInteger()) {
+            maxDepth = Math.max(maxDepth, depth);
+        }
+        else {
+            for (NestedInteger i : n.getList()) {
+                updateMaxDepth(i, depth+1);
+            }
+        }
+    }
+}
