[Function add]

Seanforfun · Seanforfun · commit 9b3ed4192c3c · 2019-04-12T17:56:28.000-04:00
1. Add leetcode solutions with tag BST.
diff --git a/README.md b/README.md
@@ -697,6 +697,28 @@
 * [337. House Robber III](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/337.%20House%20Robber%20III.md)
 * [979. Distribute Coins in Binary Tree](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/979.%20Distribute%20Coins%20in%20Binary%20Tree.md)
 
+### Binary Search
+* [34. Find First and Last Position of Element in Sorted Array](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/34.%20Find%20First%20and%20Last%20Position%20of%20Element%20in%20Sorted%20Array.md)
+* [35. Search Insert Position](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/35.%20Search%20Insert%20Position.md)
+* [704. Binary Search](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/704.%20Binary%20Search.md)
+* [981. Time Based Key-Value Store](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/981.%20Time%20Based%20Key-Value%20Store.md)
+* [33. Search in Rotated Sorted Array](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/33.%20Search%20in%20Rotated%20Sorted%20Array.md)
+* [81. Search in Rotated Sorted Array II](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/81.%20Search%20in%20Rotated%20Sorted%20Array%20II.md)
+* [153. Find Minimum in Rotated Sorted Array](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/153.%20Find%20Minimum%20in%20Rotated%20Sorted%20Array.md)
+* [154. Find Minimum in Rotated Sorted Array II](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/154.%20Find%20Minimum%20in%20Rotated%20Sorted%20Array%20II.md)
+* [162. Find Peak Element](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/162.%20Find%20Peak%20Element.md)
+* [852. Peak Index in a Mountain Array](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/852.%20Peak%20Index%20in%20a%20Mountain%20Array.md)
+* [69. Sqrt(x)](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/69.%20Sqrt(x).md)
+* [74. Search a 2D Matrix](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/74.%20Search%20a%202D%20Matrix.md)
+* [378. Kth Smallest Element in a Sorted Matrix](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/378.%20Kth%20Smallest%20Element%20in%20a%20Sorted%20Matrix.md)
+* [668. Kth Smallest Number in Multiplication Table](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/668.%20Kth%20Smallest%20Number%20in%20Multiplication%20Table.md)
+* [778. Swim in Rising Water](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/778.%20Swim%20in%20Rising%20Water.md)
+* [174. Dungeon Game](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/174.%20Dungeon%20Game.md)
+* [875. Koko Eating Bananas](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/875.%20Koko%20Eating%20Bananas.md)
+* [4.Median of Two Sorted Arrays](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/4.%20Median%20of%20Two%20Sorted%20Arrays.md)
+* [719. Find K-th Smallest Pair Distance](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/719.%20Find%20K-th%20Smallest%20Pair%20Distance.md)
+* [786. K-th Smallest Prime Fraction](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/786.%20K-th%20Smallest%20Prime%20Fraction.md)
+
 ## Algorithm(4th_Edition)
 Reading notes of book Algorithm(4th Algorithm),ISBN: 9787115293800.
 All java realization codes are placed in different packages.
diff --git a/leetcode/108. Convert Sorted Array to Binary Search Tree.md b/leetcode/108. Convert Sorted Array to Binary Search Tree.md
@@ -77,4 +77,33 @@ class Solution {
         return node;
     }
 }
-```
+```
+
+### Third Time
+* Method 1: BST + binary search
+	```Java
+	/**
+	 * Definition for a binary tree node.
+	 * public class TreeNode {
+	 *     int val;
+	 *     TreeNode left;
+	 *     TreeNode right;
+	 *     TreeNode(int x) { val = x; }
+	 * }
+	 */
+	class Solution {
+		private int[] nums;
+		public TreeNode sortedArrayToBST(int[] nums) {
+			this.nums = nums;
+			return createTree(0, nums.length - 1);
+		}
+		private TreeNode createTree(int low, int high){
+			if(low > high) return null;
+			int mid = low + (high - low) / 2;
+			TreeNode node = new TreeNode(nums[mid]);
+			node.left = createTree(low, mid - 1);
+			node.right = createTree(mid + 1, high);
+			return node;
+		}
+	}
+	```
diff --git a/leetcode/230. Kth Smallest Element in a BST.md b/leetcode/230. Kth Smallest Element in a BST.md
@@ -90,3 +90,31 @@ class Solution {
     }
 }
 ```
+
+### Third Time
+* Method 1: BST
+	```Java
+	/**
+	 * Definition for a binary tree node.
+	 * public class TreeNode {
+	 *     int val;
+	 *     TreeNode left;
+	 *     TreeNode right;
+	 *     TreeNode(int x) { val = x; }
+	 * }
+	 */
+	class Solution {
+		private List<Integer> res;
+		public int kthSmallest(TreeNode root, int k) {
+			this.res = new ArrayList<>();
+			dfs(root, k);
+			return this.res.get(k - 1);
+		}
+		private void dfs(TreeNode node, int k){
+			if(node == null || res.size() > k) return;
+			dfs(node.left, k);
+			this.res.add(node.val);
+			dfs(node.right, k);
+		}
+	}
+	```
diff --git a/leetcode/501. Find Mode in Binary Search Tree.md b/leetcode/501. Find Mode in Binary Search Tree.md
@@ -0,0 +1,71 @@
+## 501. Find Mode in Binary Search Tree
+
+### Question
+Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.
+
+Assume a BST is defined as follows:
+* The left subtree of a node contains only nodes with keys less than or equal to the node's key.
+* The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
+* Both the left and right subtrees must also be binary search trees.
+
+ 
+```
+For example:
+Given BST [1,null,2,2],
+
+   1
+    \
+     2
+    /
+   2
+
+ 
+
+return [2].
+```
+
+Note: If a tree has more than one mode, you can return them in any order.
+
+Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).
+
+### Solution
+* Method 1: HashMap + dfs
+	```Java
+	/**
+	 * Definition for a binary tree node.
+	 * public class TreeNode {
+	 *     int val;
+	 *     TreeNode left;
+	 *     TreeNode right;
+	 *     TreeNode(int x) { val = x; }
+	 * }
+	 */
+	class Solution {
+		private Map<Integer, Integer> map;
+		private int max = Integer.MIN_VALUE;
+		public int[] findMode(TreeNode root) {
+			if(root == null) return new int[]{};
+			this.map = new HashMap<>();
+			dfs(root);
+			int count = 0;
+			for(int i : map.values()){
+				if(i == max) count++;
+			}
+			int[] res = new int[count];
+			int i = 0;
+			for(Map.Entry<Integer, Integer> entry : map.entrySet()){
+				if(entry.getValue() == max)
+					res[i++] = entry.getKey();
+			}
+			return res;
+		}
+		private void dfs(TreeNode node){
+			if(node == null) return;
+			Integer count = map.containsKey(node.val) ? map.get(node.val): 0;
+			map.put(node.val, count + 1);
+			this.max = Math.max(max, count + 1);
+			dfs(node.left);
+			dfs(node.right);
+		}
+	}
+	```
diff --git a/leetcode/530. Minimum Absolute Difference in BST.md b/leetcode/530. Minimum Absolute Difference in BST.md
@@ -0,0 +1,63 @@
+## 530. Minimum Absolute Difference in BST
+
+### Question:
+Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.
+
+```
+Example:
+
+Input:
+
+   1
+    \
+     3
+    /
+   2
+
+Output:
+1
+
+Explanation:
+The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).
+```
+
+Note: There are at least two nodes in this BST.
+
+
+### Solution:
+* Method 1: BST
+    ```Java
+    /**
+     * Definition for a binary tree node.
+     * public class TreeNode {
+     *     int val;
+     *     TreeNode left;
+     *     TreeNode right;
+     *     TreeNode(int x) { val = x; }
+     * }
+     */
+    class Solution {
+        private int res = Integer.MAX_VALUE;
+        public int getMinimumDifference(TreeNode root) {
+            int[] range = getRange(root);
+            return this.res;
+        }
+        private int[] getRange(TreeNode node){
+            int cur = node.val;
+            int[] left = null, right = null;
+            if(node.left != null){
+                left = getRange(node.left);
+                this.res = Math.min(res, cur - left[1]);
+            }
+            if(node.right != null){
+                right = getRange(node.right);
+                this.res = Math.min(res, right[0] - cur);
+            }
+            if(left == null && right == null) return new int[]{cur, cur};
+            else if(left != null && right != null) return new int[]{left[0], right[1]};
+            else{
+                return left == null ? new int[]{cur, right[1]}: new int[]{left[0], cur};
+            }
+        }
+    }
+    ```
diff --git a/leetcode/700. Search in a Binary Search Tree.md b/leetcode/700. Search in a Binary Search Tree.md
@@ -0,0 +1,48 @@
+## 700. Search in a Binary Search Tree
+
+### Question:
+Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node's value equals the given value. Return the subtree rooted with that node. If such node doesn't exist, you should return NULL.
+
+```
+For example, 
+
+Given the tree:
+        4
+       / \
+      2   7
+     / \
+    1   3
+
+And the value to search: 2
+
+You should return this subtree:
+
+      2     
+     / \   
+    1   3
+
+In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL.
+```
+
+Note that an empty tree is represented by NULL, therefore you would see the expected output (serialized tree format) as [], not null.
+
+### Solution:
+* Method 1: BST
+    ```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 searchBST(TreeNode root, int val) {
+            if(root == null) return null;
+            if(root.val == val) return root;
+            return searchBST(val < root.val ? root.left: root.right, val);
+        }
+    }
+    ```
diff --git a/leetcode/701. Insert into a Binary Search Tree.md b/leetcode/701. Insert into a Binary Search Tree.md
@@ -0,0 +1,59 @@
+## 701. Insert into a Binary Search Tree
+
+### Question
+Given the root node of a binary search tree (BST) and a value to be inserted into the tree, insert the value into the BST. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.
+
+Note that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.
+
+```
+For example, 
+
+Given the tree:
+        4
+       / \
+      2   7
+     / \
+    1   3
+And the value to insert: 5
+
+You can return this binary search tree:
+
+         4
+       /   \
+      2     7
+     / \   /
+    1   3 5
+
+This tree is also valid:
+
+         5
+       /   \
+      2     7
+     / \   
+    1   3
+         \
+          4
+```
+
+### Solution
+* Method 1: BST, recursion
+	```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 insertIntoBST(TreeNode root, int val) {
+			if(root == null) return new TreeNode(val);
+			if(val < root.val){
+				root.left = insertIntoBST(root.left, val);
+			}else root.right = insertIntoBST(root.right, val);
+			return root;
+		}
+	}
+	```
diff --git a/leetcode/786. K-th Smallest Prime Fraction.md b/leetcode/786. K-th Smallest Prime Fraction.md
diff --git a/leetcode/98. Validate Binary Search Tree.md b/leetcode/98. Validate Binary Search Tree.md
diff --git a/leetcode/99. Recover Binary Search Tree.md b/leetcode/99. Recover Binary Search Tree.md
