[Function add]

Seanforfun · Seanforfun · commit 1eefca6be59a · 2019-04-08T12:36:46.000-04:00
1. Add leetcode solutions with tag tree.
diff --git a/leetcode/669. Trim a Binary Search Tree.md b/leetcode/669. Trim a Binary Search Tree.md
@@ -0,0 +1,83 @@
+## 669. Trim a Binary Search Tree
+
+### Question:
+ Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.
+
+```
+Example 1:
+
+Input: 
+    1
+   / \
+  0   2
+
+  L = 1
+  R = 2
+
+Output: 
+    1
+      \
+       2
+
+Example 2:
+
+Input: 
+    3
+   / \
+  0   4
+   \
+    2
+   /
+  1
+
+  L = 1
+  R = 3
+
+Output: 
+      3
+     / 
+   2   
+  /
+ 1
+```
+
+
+### Solution:
+* Method 1: divide and conquer (O(V + E), time complexity of dfs )
+    * divide: we do the trim for left and right node.
+    * if current node is within the range, we just return current node.
+    * if current node needs to be trimmed, we need to append the right node to the very right of left subtree and return the left node of current node.
+    ```Java
+    /**
+     * Definition for a binary tree node.
+     * public class TreeNode {
+     *     int val;
+     *     TreeNode left;
+     *     TreeNode right;
+     *     TreeNode(int x) { val = x; }
+     * }
+     */
+    class Solution {
+        public TreeNode trimBST(TreeNode root, int L, int R) {
+            if(root == null) return root;
+            TreeNode left = trimBST(root.left, L, R);
+            root.left = left;
+            TreeNode right = trimBST(root.right, L, R);
+            root.right = right;
+            if(root.val < L || root.val > R){
+                if(root.left == null) return root.right;
+                else{
+                    TreeNode node = root.left;
+                    while(node.right != null){
+                        node = node.right;
+                    }
+                    node.right = root.right;
+                    root.right = null;
+                    return root.left;
+                }
+            }
+            return root;
+        }
+    }
+    ```
+   
diff --git a/leetcode/814. Binary Tree Pruning.md b/leetcode/814. Binary Tree Pruning.md
@@ -0,0 +1,105 @@
+## 814. Binary Tree Pruning
+
+### Question:
+We are given the head node root of a binary tree, where additionally every node's value is either a 0 or a 1.
+
+Return the same tree where every subtree (of the given tree) not containing a 1 has been removed.
+
+(Recall that the subtree of a node X is X, plus every node that is a descendant of X.)
+
+```
+Example 1:
+Input: [1,null,0,0,1]
+Output: [1,null,0,null,1]
+ 
+Explanation: 
+Only the red nodes satisfy the property "every subtree not containing a 1".
+The diagram on the right represents the answer.
+
+
+Example 2:
+Input: [1,0,1,0,0,0,1]
+Output: [1,null,1,null,1]
+
+Example 3:
+Input: [1,1,0,1,1,0,1,0]
+Output: [1,1,0,1,1,null,1]
+```
+
+Note:
+1. The binary tree will have at most 100 nodes.
+2, The value of each node will only be 0 or 1.
+
+
+### Solution:
+* Method 1: recursion
+   * For this question must make sure that for a single node, we need 2 flags for indicating left and right can be removed, we should initialize them as true.
+    ```Java
+    /**
+     * Definition for a binary tree node.
+     * public class TreeNode {
+     *     int val;
+     *     TreeNode left;
+     *     TreeNode right;
+     *     TreeNode(int x) { val = x; }
+     * }
+     */
+    class Solution {
+        public TreeNode pruneTree(TreeNode root) {
+            if(root == null) return root;
+            boolean left = true, right = true;
+            if(root.left != null){
+                left = pruneNode(root.left);
+                if(left) root.left = null;
+            }
+            if(root.right != null){
+                right = pruneNode(root.right);
+                if(right) root.right = null;
+            }
+            if(left && right && root.val == 0){
+                root = null;
+            }
+            return root;
+        }
+        private boolean pruneNode(TreeNode node){
+            if(node.val == 0 && node.left == null && node.right == null) return true;
+            else{
+                boolean left = true, right = true;
+                if(node.left != null){
+                    left = pruneNode(node.left);
+                    if(left) node.left = null;
+                }
+                if(node.right != null){
+                    right = pruneNode(node.right);
+                    if(right) node.right = null;
+                }
+                return (left && right) && node.val == 0;
+            }
+        }
+    }
+    ```
+
+* Method 2: Divide and conquer
+    ```Java
+    /**
+     * Definition for a binary tree node.
+     * public class TreeNode {
+     *     int val;
+     *     TreeNode left;
+     *     TreeNode right;
+     *     TreeNode(int x) { val = x; }
+     * }
+     */
+    class Solution {
+        public TreeNode pruneTree(TreeNode root){
+            if(root == null) return root;
+            TreeNode left = pruneTree(root.left);
+            root.left = left;
+            TreeNode right = pruneTree(root.right);
+            root.right = right;
+            if(root.val == 0 && root.left == null && root.right == null)
+                root = null;
+            return root;
+        }
+    }
+    ```
diff --git a/leetcode/987. Vertical Order Traversal of a Binary Tree.md b/leetcode/987. Vertical Order Traversal of a Binary Tree.md
@@ -0,0 +1,89 @@
+## 987. Vertical Order Traversal of a Binary Tree
+
+### Question:
+Given a binary tree, return the vertical order traversal of its nodes values.
+
+For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1).
+
+Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).
+
+If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.
+
+Return an list of non-empty reports in order of X coordinate.  Every report will have a list of values of nodes.
+
+```
+Example 1:
+
+Input: [3,9,20,null,null,15,7]
+Output: [[9],[3,15],[20],[7]]
+Explanation: 
+Without loss of generality, we can assume the root node is at position (0, 0):
+Then, the node with value 9 occurs at position (-1, -1);
+The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);
+The node with value 20 occurs at position (1, -1);
+The node with value 7 occurs at position (2, -2).
+
+Example 2:
+
+Input: [1,2,3,4,5,6,7]
+Output: [[4],[2],[1,5,6],[3],[7]]
+Explanation: 
+The node with value 5 and the node with value 6 have the same position according to the given scheme.
+However, in the report "[1,5,6]", the node value of 5 comes first since 5 is smaller than 6.
+```
+
+Note:
+1. The tree will have between 1 and 1000 nodes.
+2. Each node's value will be between 0 and 1000.
+
+
+
+### Solution:
+* Method 1: DFS + TreeMap, dfs is for giving coordinators to nodes and TreeMap is for order.
+    *Time complexity: dfs(O(Vertice + Edge)) + TreeMap(O(NlogN))
+    ```Java
+    /**
+     * Definition for a binary tree node.
+     * public class TreeNode {
+     *     int val;
+     *     TreeNode left;
+     *     TreeNode right;
+     *     TreeNode(int x) { val = x; }
+     * }
+     */
+    class Solution {
+        private TreeMap<Integer, TreeMap<Integer, PriorityQueue<Integer>>> map;
+        public List<List<Integer>> verticalTraversal(TreeNode root) {
+            map = new TreeMap<>();
+            List<List<Integer>> result = new ArrayList<>();
+            if(root == null) return result;
+            dfs(0, 0, root);
+            for(TreeMap<Integer, PriorityQueue<Integer>> value : map.values()){
+                List<Integer> temp = new ArrayList<>();
+                for(PriorityQueue<Integer> pq : value.values()){
+                    while(!pq.isEmpty()){
+                        temp.add(pq.poll());
+                    }
+                }
+                result.add(temp);
+            }
+            return result;
+        }
+        private void dfs(int x, int y, TreeNode node){
+            TreeMap<Integer, PriorityQueue<Integer>> value = map.containsKey(x) ? map.get(x): new TreeMap<Integer, PriorityQueue<Integer>>(
+                new Comparator<Integer>(){
+                    @Override
+                    public int compare(Integer n1, Integer n2){
+                        return n2 - n1;
+                    }
+                }
+            );
+            PriorityQueue<Integer> pq = value.containsKey(y) ? value.get(y): new PriorityQueue<Integer>();
+            pq.offer(node.val);
+            value.put(y, pq);
+            map.put(x, value);
+            if(node.left != null) dfs(x - 1, y - 1, node.left);
+            if(node.right != null) dfs(x + 1, y - 1, node.right);
+        }
+    }
+    ```
