[Function add]: 1. Add leetcode solutions with tage tree.

Botao Xiao · Botao Xiao · commit 7bf0c269a1ca · 2019-04-08T22:51:16.000-04:00
diff --git a/leetcode/102. Binary Tree Level Order Traversal.md b/leetcode/102. Binary Tree Level Order Traversal.md
@@ -91,4 +91,38 @@ class Solution {
         return result;
     }
 }
-```
+```
+
+### Third Time
+* Method 1: bfs
+  ```Java
+  /**
+   * 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>> levelOrder(TreeNode root) {
+          List<List<Integer>> result = new ArrayList<>();
+          if(root == null) return result;
+          Queue<TreeNode> q = new LinkedList<>();
+          q.offer(root);
+          while(!q.isEmpty()){
+              List<Integer> temp = new ArrayList<>();
+              int size = q.size();
+              for(int i = 0; i < size; i++){
+                  TreeNode node = q.poll();
+                  temp.add(node.val);
+                  if(node.left != null) q.offer(node.left);
+                  if(node.right != null) q.offer(node.right);
+              }
+              result.add(temp);
+          }
+          return result;
+      }
+  }
+  ```
diff --git a/leetcode/107. Binary Tree Level Order Traversal II.md b/leetcode/107. Binary Tree Level Order Traversal II.md
@@ -92,4 +92,39 @@ class Solution {
         return result;
     }
 }
-```
+```
+
+### Third Time
+* Method 1: BFS
+  ```Java
+  /**
+   * 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>> levelOrderBottom(TreeNode root) {
+          List<List<Integer>> result = new ArrayList<>();
+          if(root == null) return result;
+          Queue<TreeNode> q = new LinkedList<>();
+          q.offer(root);
+          while(!q.isEmpty()){
+              List<Integer> temp = new ArrayList<>();
+              int size = q.size();
+              for(int i = 0; i < size; i++){
+                  TreeNode node = q.poll();
+                  temp.add(node.val);
+                  if(node.left != null) q.offer(node.left);
+                  if(node.right != null) q.offer(node.right);
+              }
+              result.add(temp);
+          }
+          Collections.reverse(result);
+          return result;
+      }
+  }
+  ```
diff --git a/leetcode/297. Serialize and Deserialize Binary Tree.md b/leetcode/297. Serialize and Deserialize Binary Tree.md
@@ -93,7 +93,7 @@ public class Codec {
 public class Codec {
     private final String split = ",";
     private final String empty = "#";
-    
+
     // Encodes a tree to a single string.
     public String serialize(TreeNode root) {
         StringBuilder sb = new StringBuilder();
@@ -131,4 +131,57 @@ public class Codec {
 // Your Codec object will be instantiated and called as such:
 // Codec codec = new Codec();
 // codec.deserialize(codec.serialize(root));
-```
+```
+
+### Third Time
+* Method 1: dfs
+  ```Java
+  /**
+   * Definition for a binary tree node.
+   * public class TreeNode {
+   *     int val;
+   *     TreeNode left;
+   *     TreeNode right;
+   *     TreeNode(int x) { val = x; }
+   * }
+   */
+  public class Codec {
+      private static final String EMPTY = "#";
+      private static final String SPLIT = ",";
+      // Encodes a tree to a single string.
+      public String serialize(TreeNode root) {
+          StringBuilder sb = new StringBuilder();
+          serialize(root, sb);
+          return sb.toString();
+      }
+      private void serialize(TreeNode node, StringBuilder sb){
+          if(node == null){
+              sb.append(EMPTY).append(SPLIT);
+          }else{
+              sb.append(node.val).append(SPLIT);
+              serialize(node.left, sb);
+              serialize(node.right, sb);
+          }
+      }
+      // Decodes your encoded data to tree.
+      public TreeNode deserialize(String data) {
+          String[] tokens = data.split(SPLIT);
+          LinkedList<String> q = new LinkedList<>();
+          q.addAll(Arrays.asList(tokens));
+          return deserialize(q);
+      }
+      private TreeNode deserialize(LinkedList<String> q){
+          String token = q.poll();
+          if(token.equals(EMPTY)) return null;
+          else{
+              TreeNode node = new TreeNode(Integer.parseInt(token));
+              node.left = deserialize(q);
+              node.right = deserialize(q);
+              return node;
+          }
+      }
+  }
+  // Your Codec object will be instantiated and called as such:
+  // Codec codec = new Codec();
+  // codec.deserialize(codec.serialize(root));
+  ```
diff --git a/leetcode/449. Serialize and Deserialize BST.md b/leetcode/449. Serialize and Deserialize BST.md
@@ -0,0 +1,118 @@
+## 449. Serialize and Deserialize BST
+
+### Question
+Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
+
+Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.
+
+The encoded string should be as compact as possible.
+
+Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
+
+### Solution:
+* Method 1: dfs
+  ```Java
+  /**
+   * Definition for a binary tree node.
+   * public class TreeNode {
+   *     int val;
+   *     TreeNode left;
+   *     TreeNode right;
+   *     TreeNode(int x) { val = x; }
+   * }
+   */
+  public class Codec {
+      private static final String empty = "#";
+      private static final String split = ",";
+      // Encodes a tree to a single string.
+      public String serialize(TreeNode root) {
+          StringBuilder sb = new StringBuilder();
+          serialize(root, sb);
+          return sb.toString();
+      }
+      private void serialize(TreeNode node, StringBuilder sb){
+          if(node == null){
+              sb.append(empty).append(split);
+          }else{
+              sb.append(node.val).append(split);
+              serialize(node.left, sb);
+              serialize(node.right, sb);
+          }
+      }
+      // Decodes your encoded data to tree.
+      public TreeNode deserialize(String data) {
+          String[] tokens = data.split(split);
+          LinkedList<String> q = new LinkedList<>();
+          q.addAll(Arrays.asList(tokens));
+          return deserialize(q);
+      }
+      private TreeNode deserialize(Queue<String> q){
+          String token = q.poll();
+          if(token.equals(empty)) return null;
+          else{
+              TreeNode node = new TreeNode(Integer.parseInt(token));
+              node.left = deserialize(q);
+              node.right = deserialize(q);
+              return node;
+          }
+      }
+  }
+
+  // Your Codec object will be instantiated and called as such:
+  // Codec codec = new Codec();
+  // codec.deserialize(codec.serialize(root));
+  ```
+
+* Method 2: Use the property of BST
+  ```Java
+  /**
+   * Definition for a binary tree node.
+   * public class TreeNode {
+   *     int val;
+   *     TreeNode left;
+   *     TreeNode right;
+   *     TreeNode(int x) { val = x; }
+   * }
+   */
+  public class Codec {
+
+      // Encodes a tree to a single string.
+      public String serialize(TreeNode root) {
+          StringBuilder sb = new StringBuilder();
+          dfs(root, sb);
+          return sb.toString();
+      }
+      private void dfs(TreeNode node, StringBuilder sb){
+          if(node == null) return;
+          else{
+              sb.append(node.val).append(",");
+              dfs(node.left, sb);
+              dfs(node.right, sb);
+          }
+      }
+
+      // Decodes your encoded data to tree.
+      public TreeNode deserialize(String data) {
+          if(data.trim().length() == 0) return null;
+          String[] tokens = data.split(",");
+          TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
+          for(int i = 1; i < tokens.length; i++){
+              insert(root, Integer.parseInt(tokens[i]));
+          }
+          return root;
+      }
+      private TreeNode insert(TreeNode node, int num){
+          if(node == null) return new TreeNode(num);
+          else if(num < node.val || node.val == num){
+              node.left = insert(node.left, num);
+          }else if(num > node.val){
+              node.right = insert(node.right, num);
+          }
+          return node;
+      }
+  }
+
+  // Your Codec object will be instantiated and called as such:
+  // Codec codec = new Codec();
+  // codec.deserialize(codec.serialize(root));
+  ```
diff --git a/leetcode/508. Most Frequent Subtree Sum.md b/leetcode/508. Most Frequent Subtree Sum.md
@@ -0,0 +1,75 @@
+## 508. Most Frequent Subtree Sum
+
+### Question
+Given the root of a tree, you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order.
+
+```
+Examples 1
+Input:
+
+  5
+ /  \
+2   -3
+return [2, -3, 4], since all the values happen only once, return all of them in any order.
+Examples 2
+Input:
+
+  5
+ /  \
+2   -5
+return [2], since 2 happens twice, however -5 only occur once.
+```
+
+Note: You may assume the sum of values in any subtree is in the range of 32-bit signed integer.
+
+### Solution
+* Method 1: dfs + Map
+  ```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;
+      public int[] findFrequentTreeSum(TreeNode root) {
+          this.map = new HashMap<>();
+          if(root == null) return new int[]{};
+          getSubtreeSum(root);
+          List<Integer> res = new ArrayList<>();
+          for(Map.Entry<Integer, Integer> entry: map.entrySet()){
+              if(entry.getValue() == max){
+                  res.add(entry.getKey());
+              }
+          }
+          int size = res.size();
+          int index = 0;
+          int[] result = new int[size];
+          for(Integer n : res)
+              result[index++] = n;
+          return result;
+      }
+      private int getSubtreeSum(TreeNode node){
+          if(node.left == null && node.right == null){
+              int appear = map.containsKey(node.val) ? map.get(node.val): 0;
+              map.put(node.val, appear + 1);
+              max = Math.max(max, appear + 1);
+              return node.val;
+          }else{
+              int left = 0, right = 0;
+              if(node.left != null) left = getSubtreeSum(node.left);
+              if(node.right != null) right = getSubtreeSum(node.right);
+              int sum = node.val + left + right;
+              int appearSum = map.containsKey(sum) ? map.get(sum): 0;
+              map.put(sum, appearSum + 1);
+              max = Math.max(max, appearSum + 1);
+              return sum;
+          }
+      }
+  }
+  ```
