Commit 09/05

surajr · surajr · commit 2e16ee90ed33 · 2017-09-05T14:50:09.000-07:00
diff --git a/README.md b/README.md
@@ -65,6 +65,8 @@ Feel free to add issues, comment and pull request.
 | Leetcode  | [653. Two Sum IV - Input is a BST](https://leetcode.com/problems/two-sum-iv-input-is-a-bst/description/) | [Java](./java/Twosum.java) \| [Python](./Python/) | _O(n)_       | _O(n)_          |  Easy       |         |
 | Leetcode  | [617. Merge Two Binary Trees](https://leetcode.com/problems/merge-two-binary-trees/description/) | [Java](./java/mergeTrees.java) \| [Python](./Python/) | _O(mn)_       | _O(1)_          |  Easy       |         |
 | Leetcode  | [637. Average of Levels in Binary Tree](https://leetcode.com/problems/average-of-levels-in-binary-tree/description/) | [Java](./java/averageOfLevels.java) \| [Python](./Python/) | _O(n)_       | _O(1)_          |  Easy       |         |
+| Leetcode  | [663. Equal Tree Partition](https://leetcode.com/problems/equal-tree-partition/description/) | [Java](./java/CheckEqualTrees.java) \| [Python](./Python/) |        |           |  Medium       |         |
+| Leetcode  | [623. Add One Row to Tree](https://leetcode.com/problems/add-one-row-to-tree/description/) | [Java](./java/addOneRow.java) \| [Python](./Python/) |        |           |  Medium       |         |
 
 
 ## Dynamic Programming
diff --git a/java/CheckEqualTrees.java b/java/CheckEqualTrees.java
@@ -0,0 +1,58 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public boolean checkEqualTree(TreeNode root) {
+        
+        if(root == null)
+            return false;
+        
+        int sum = checkSum(root);
+        
+        if(sum %2 != 0)
+            return false;
+        
+        Stack<TreeNode> stack = new Stack<>();
+        stack.push(root);
+        
+        while(!stack.isEmpty())
+        {
+            TreeNode node = stack.pop();
+            
+            if(node.left != null)
+            {
+                int leftSum = checkSum(node.left);           
+                if(leftSum == sum - leftSum)
+                    return true;
+                stack.push(node.left);
+            }
+            
+            if(node.right != null)
+            {
+                int rightSum = checkSum(node.right);
+                if(rightSum == sum - rightSum)
+                    return true;
+                
+                stack.push(node.right);
+            }       
+            
+        }
+        return false;
+        
+    }
+    
+    public int checkSum(TreeNode root)
+    {
+        if(root == null)
+            return 0;
+        
+        return root.val + checkSum(root.left) + checkSum(root.right);
+    }
+  
+}
diff --git a/java/addOneRow.java b/java/addOneRow.java
@@ -0,0 +1,46 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public TreeNode addOneRow(TreeNode root, int v, int d) {
+        
+        if(d == 1)
+        {
+            TreeNode result = new TreeNode(v);
+            result.left = root;
+            return result;
+        }
+        
+        dfs(root, 1, v, d);
+        return root;        
+    }
+    
+    public void dfs(TreeNode root, int depth, int v, int d)
+    {
+        if(root == null)
+            return;
+        
+        if(depth < d-1)
+        {
+            dfs(root.left, depth+1, v, d);
+            dfs(root.right, depth+1, v, d);
+        }
+        else
+        {
+            TreeNode result = root.left;
+            root.left = new TreeNode(v);
+            root.left.left = result;
+            result = root.right;
+            root.right = new TreeNode(v);
+            root.right.right = result;
+            
+            
+        }
+    }
+}
diff --git a/java/leastInterval.java b/java/leastInterval.java
@@ -0,0 +1,47 @@
+class Solution {
+    public int leastInterval(char[] tasks, int n) {
+        
+        int[] map = new int[26];
+        
+        for(char task : tasks)
+            map[task - 'A']++;
+        
+        PriorityQueue<Integer> queue = new PriorityQueue<>(26, Collections.reverseOrder());
+        
+        for(int entry : map)
+            if (entry > 0)
+                queue.offer(entry);
+        
+        int time = 0;
+        
+        while(!queue.isEmpty())
+        {
+            int i = 0;
+            List<Integer> temp = new ArrayList<>();
+            while(i <= n)
+            {                
+                if(!queue.isEmpty())
+                {
+                    if(queue.peek()>1)
+                    {
+                        temp.add(queue.poll()-1);
+                    }
+                    else
+                        queue.poll();
+                    
+                    
+                }
+                time++;
+                if(queue.isEmpty() && temp.size()==0)
+                    break;
+                i++;
+            }
+            
+            for(int a : temp)
+                queue.offer(a);
+        }
+        
+        return time;       
+        
+    }
+}
diff --git a/java/triangleNumber.java b/java/triangleNumber.java
@@ -0,0 +1,24 @@
+public class Solution {
+    public int triangleNumber(int[] nums) {
+        if(nums.length == 0)
+            return 0;
+        
+        Arrays.sort(nums);
+        int count = 0;
+        for(int i=2; i<nums.length; i++)
+        {
+            int j = 0, k = i-1;
+            while(j < k)
+            {
+                if(nums[j]+nums[k] > nums[i])
+                {
+                    count += k-j;
+                    k--;
+                }
+                else j++;
+                    
+            }
+        }
+        return count;
+    }
+}
