finish 116,117,560

BaffinLee · BaffinLee · commit 619775ea2bc1 · 2018-06-13T15:59:07.000+08:00
diff --git a/101-200/116. Populating Next Right Pointers in Each Node.md b/101-200/116. Populating Next Right Pointers in Each Node.md
@@ -0,0 +1,143 @@
+# 116. Populating Next Right Pointers in Each Node
+
+- Difficulty: Medium.
+- Related Topics: Tree, Depth-first Search.
+- Similar Questions: Populating Next Right Pointers in Each Node II, Binary Tree Right Side View.
+
+## Problem
+
+Given a binary tree
+
+```
+struct TreeLinkNode {
+  TreeLinkNode *left;
+  TreeLinkNode *right;
+  TreeLinkNode *next;
+}
+```
+
+Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to ```NULL```.
+
+Initially, all next pointers are set to ```NULL```.
+
+**Note:**
+
+
+	
+- You may only use constant extra space.
+	
+- Recursive approach is fine, implicit stack space does not count as extra space for this problem.
+	
+- You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
+
+
+**Example:**
+
+Given the following perfect binary tree,
+
+```
+1
+   /  \
+  2    3
+ / \  / \
+4  5  6  7
+```
+
+After calling your function, the tree should look like:
+
+```
+1 -> NULL
+   /  \
+  2 -> 3 -> NULL
+ / \  / \
+4->5->6->7 -> NULL
+```
+
+
+## Solution 1
+
+```javascript
+/**
+ * Definition for binary tree with next pointer.
+ * function TreeLinkNode(val) {
+ *     this.val = val;
+ *     this.left = this.right = this.next = null;
+ * }
+ */
+
+/**
+ * @param {TreeLinkNode} root
+ * @return {void} Do not return anything, modify tree in-place instead.
+ */
+var connect = function(root) {
+  var stack = [];
+  var tmp = null;
+  var node = null;
+  var next = null;
+  var level = 0;
+  
+  if (root) stack.push([root, 0]);
+  
+  while (stack.length) {
+    tmp = stack.shift();
+    node = tmp[0];
+    level = tmp[1];
+    
+    next = stack[0] && stack[0][1] === level ? stack[0][0] : null;
+    
+    node.next = next;
+    
+    if (node.left) stack.push([node.left, level + 1]);
+    if (node.right) stack.push([node.right, level + 1]);
+  }
+};
+```
+
+**Explain:**
+
+nope.
+
+**Complexity:**
+
+* Time complexity : O(n).
+* Space complexity : O(n).
+
+## Solution 2
+
+```javascript
+/**
+ * Definition for binary tree with next pointer.
+ * function TreeLinkNode(val) {
+ *     this.val = val;
+ *     this.left = this.right = this.next = null;
+ * }
+ */
+
+/**
+ * @param {TreeLinkNode} root
+ * @return {void} Do not return anything, modify tree in-place instead.
+ */
+var connect = function(root) {
+  if (!root) return;
+  var now = root;
+  var cur = null;
+  while (now.left) {
+    cur = now;
+    while (cur) {
+      cur.left.next = cur.right;
+      if (cur.next) cur.right.next = cur.next.left;
+      cur = cur.next;
+    }
+    now = now.left;
+  }
+};
+```
+
+**Explain:**
+
+nope.
+
+**Complexity:**
+
+* Time complexity : O(n).
+* Space complexity : O(1).
diff --git a/101-200/117. Populating Next Right Pointers in Each Node II.md b/101-200/117. Populating Next Right Pointers in Each Node II.md
@@ -0,0 +1,139 @@
+# 117. Populating Next Right Pointers in Each Node II
+
+- Difficulty: Medium.
+- Related Topics: Tree, Depth-first Search.
+- Similar Questions: Populating Next Right Pointers in Each Node.
+
+## Problem
+
+Given a binary tree
+
+```
+struct TreeLinkNode {
+  TreeLinkNode *left;
+  TreeLinkNode *right;
+  TreeLinkNode *next;
+}
+```
+
+Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to ```NULL```.
+
+Initially, all next pointers are set to ```NULL```.
+
+**Note:**
+
+- You may only use constant extra space.
+- Recursive approach is fine, implicit stack space does not count as extra space for this problem.
+
+**Example:**
+
+Given the following binary tree,
+
+```
+    1
+   /  \
+  2    3
+ / \    \
+4   5    7
+```
+
+After calling your function, the tree should look like:
+
+```
+     1 -> NULL
+   /  \
+  2 -> 3 -> NULL
+ / \    \
+4-> 5 -> 7 -> NULL
+```
+
+## Solution 1
+
+```javascript
+/**
+ * Definition for binary tree with next pointer.
+ * function TreeLinkNode(val) {
+ *     this.val = val;
+ *     this.left = this.right = this.next = null;
+ * }
+ */
+
+/**
+ * @param {TreeLinkNode} root
+ * @return {void} Do not return anything, modify tree in-place instead.
+ */
+var connect = function(root) {
+  var stack = [];
+  var tmp = null;
+  var node = null;
+  var next = null;
+  var level = 0;
+  
+  if (root) stack.push([root, 0]);
+  
+  while (stack.length) {
+    tmp = stack.shift();
+    node = tmp[0];
+    level = tmp[1];
+    
+    next = stack[0] && stack[0][1] === level ? stack[0][0] : null;
+    
+    node.next = next;
+    
+    if (node.left) stack.push([node.left, level + 1]);
+    if (node.right) stack.push([node.right, level + 1]);
+  }
+};
+```
+
+**Explain:**
+
+nope.
+
+**Complexity:**
+
+* Time complexity : O(n).
+* Space complexity : O(n).
+
+## Solution 2
+
+```javascript
+/**
+ * Definition for binary tree with next pointer.
+ * function TreeLinkNode(val) {
+ *     this.val = val;
+ *     this.left = this.right = this.next = null;
+ * }
+ */
+
+/**
+ * @param {TreeLinkNode} root
+ * @return {void} Do not return anything, modify tree in-place instead.
+ */
+var connect = function(root) {
+  var now = root;
+  var cur = null;
+  var tmp = null;
+  var last = null;
+  while (now) {
+    tmp = new TreeLinkNode(0);
+    last = tmp;
+    cur = now;
+    while (cur) {
+      if (cur.left) { last.next = cur.left; last = last.next; }
+      if (cur.right) { last.next = cur.right; last = last.next; }
+      cur = cur.next;
+    }
+    now = tmp.next;
+  }
+};
+```
+
+**Explain:**
+
+nope.
+
+**Complexity:**
+
+* Time complexity : O(n).
+* Space complexity : O(1).
diff --git a/501-600/560. Subarray Sum Equals K.md b/501-600/560. Subarray Sum Equals K.md
@@ -0,0 +1,57 @@
+# 560. Subarray Sum Equals K
+
+- Difficulty: Medium.
+- Related Topics: Array, Hash Table.
+- Similar Questions: Two Sum, Continuous Subarray Sum, Subarray Product Less Than K, Find Pivot Index.
+
+## Problem
+
+Given an array of integers and an integer **k**, you need to find the total number of continuous subarrays whose sum equals to **k**.
+
+**Example 1:**
+```
+Input:nums = [1,1,1], k = 2
+Output: 2
+```
+
+**Note:**
+
+- The length of the array is in range [1, 20,000].
+- The range of numbers in the array is [-1000, 1000] and the range of the integer **k** is [-1e7, 1e7].
+
+## Solution
+
+```javascript
+/**
+ * @param {number[]} nums
+ * @param {number} k
+ * @return {number}
+ */
+var subarraySum = function(nums, k) {
+  var map = {};
+  var len = nums.length;
+  var sum = 0;
+  var res = 0;
+  
+  map[0] = 1;
+  
+  for (var i = 0; i < len; i++) {
+    sum += nums[i];
+    res += (map[sum - k] || 0);
+    map[sum] = (map[sum] || 0) + 1;
+  }
+  
+  return res;
+};
+```
+
+**Explain:**
+
+在 `i` 处，`map[key]` 表示 `0 ~ i` 中和为 `key` 的子数组数量。
+
+在 `i` 处，`0 ~ i` 的和为 `sum`，此前和为 `k` 的子数组个数为 `map[sum - k]`。
+
+**Complexity:**
+
+* Time complexity : O(n).
+* Space complexity : O(n).
