4. Ugly Number

1*2(t2) 2*2 3*2
(t3)1*3 2*3 3*3
(t5)1*5 2*5 3*5


1*2 2*2(t2) 3*2
1*3(t3) 2*3 3*3
(t5)1*5 2*5 3*5


Solution:
public int nthUglyNumber(int n) {
if(n == 1) return 1;
      int t2 = 0, t3 = 0, t5 = 0;
      int[] k = new int[n];
      k[0] = 1;
      for(int i = 1; i < n; i++) {
          k[i] = Math.min(Math.min(k[t2] * 2, k[t3] * 3), k[t5] * 5);
          if (k[i] == k[t2] * 2) t2++;
          if (k[i] == k[t3] * 3) t3++;
          if (k[i] == k[t5] * 5) t5++;
      }
      
      return k[n-1];
}

12. Min Stack

Solution:

1) LinkedList
Node head;
    public MinStack() {
        // do intialization if necessary
        head = null;
    }

    /*
     * @param number: An integer
     * @return: nothing
     */
    public void push(int number) {
        // write your code here
      if (head == null) {
          head = new Node(number, number, null);
      } else {
          head = new Node(number, Math.min(number, head.min), head);
      }
    }

    /*
     * @return: An integer
     */
    public int pop() {
        // write your code here
        int rst = head.val;
        head = head.next;
        return rst;
    }

    /*
     * @return: An integer
     */
    public int min() {
        // write your code here
        return head.min;
    }
   
    private class Node {
        int val;
        int min;
        Node next;
        public Node(int val, int min, Node next) {
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }


2) Two stack
Deque<Integer> s1;
    Deque<Integer> s2;
   
    public MinStack() {
        s1 = new ArrayDeque<Integer>();
        s2 = new ArrayDeque<Integer>();
    }
   
    public void push(int number) {
        s1.push(number);
        if (s2.isEmpty() || number <= min()) s2.push(number);
    }
   
    public int pop() {
        if (s1.peek() == min()) s2.pop();
        return s1.pop();
    }
   
    public int min() {
        return s2.peek();
    }

104. Merge K Sorted Lists

Solution:
1) Divide and Conquer:
/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
     
    private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        
        
        ListNode rst = null;
        ListNode dummy = null;
        while(list1 != null && list2 != null) {
            int val = 0;
            if (list1.val < list2.val) {
                val = list1.val;
                list1 = list1.next;
            } else {
                val = list2.val;
                list2 = list2.next;
            }
            
            if(dummy == null) {
                dummy = new ListNode(val);
                rst = dummy;
            } else {
                dummy.next = new ListNode(val);
                dummy = dummy.next;
            }
            
        }
        
        if (list1 == null) dummy.next = list2;
        if (list2 == null) dummy.next = list1;
        
        return rst;
        
    }
    public ListNode mergeKLists(List<ListNode> lists) {  
        // write your code here
        if (lists.size() == 0) return null;
        if (lists.size() == 1) return lists.get(0);
        if (lists.size() == 2) return mergeTwoLists(lists.get(0), lists.get(1));
        return mergeTwoLists(
            mergeKLists(lists.subList(0, lists.size()/2)), 
            mergeKLists(lists.subList(lists.size()/2, lists.size()))
        );
    }
}

107. WordBreak

LintCode:
private int getMaxLength(Set<String> dict) {
        int maxLength = 0;
        for (String word : dict) {
            maxLength = Math.max(maxLength, word.length());
        }
        return maxLength;
    } 

    public boolean wordBreak(String s, Set<String> dict) {
        if (s == null || s.length() == 0) {
            return true;
        }

        int maxLength = getMaxLength(dict);
        boolean[] canSegment = new boolean[s.length() + 1];

        canSegment[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            canSegment[i] = false;
            for (int lastWordLength = 1;
                     lastWordLength <= maxLength && lastWordLength <= i;
                     lastWordLength++) {
                if (!canSegment[i - lastWordLength]) {
                    continue;
                }
                String word = s.substring(i - lastWordLength, i);
                if (dict.contains(word)) {
                    canSegment[i] = true;
                    break;
                }
            }
        }

        return canSegment[s.length()];
    }


LeetCode ：
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s == null || s.length() == 0) {
            return false;
        }
       
      
       
        int n = s.length();
        boolean[] dp = new boolean[n];
       
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                String sub = s.substring(j, i+1);
              
                // 当这个字存在dict里，要判断要么之前已经break了要么是从头开始的word
                if (wordDict.contains(sub) && (j == 0 || dp[j - 1])) {
                    dp[i] = true;
                    break;
                }
            }
        }
       
        return dp[n - 1];
    }
}

191. Maximum Product Subarray

这道题是Maximum Subarray的follow up
应为乘法所以要考虑负负得正
所以同时记录最小值与最大值

max_products[i] = Math.max(Math.max(max_products[i-1] * nums[i],min_products[i-1]*nums[i]), nums[i])；
min_products[i] = Math.min(Math.min(max_products[i-1] * nums[i],min_products[i-1]*nums[i]), nums[i]);

public class Solution {
    /**
     * @param nums: An array of integers
     * @return: An integer
     */
    public int maxProduct(int[] nums) {
        // write your code here
        int len = nums.length;
        Integer[] max_products = new Integer[len];
        Integer[] min_products = new Integer[len];
       
        max_products[0] = nums[0];
        min_products[0] = nums[0];
        int max = max_products[0];
        for(int i = 1; i < len; i++) {
            max_products[i] = Math.max(Math.max(max_products[i-1] * nums[i],min_products[i-1]*nums[i]), nums[i]);
            min_products[i] = Math.min(Math.min(max_products[i-1] * nums[i],min_products[i-1]*nums[i]), nums[i]);
            max = Math.max(max_products[i], max);
        }
       
        return max;
    }
}

41. Maximum Subarray

现阶段的最大值等于max（前一位的最大值➕本身 ， 本身）


public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {
        // write your code here
        if (nums.length == 1) {
            return nums[0];
        }
        int len = nums.length;
        Integer[] sums = new Integer[len];

        sums[0] = nums[0];
        int max = sums[0];
        for (int i = 1; i < len; i++) {
            sums[i] = Math.max(sums[i-1] + nums[i], nums[i]);
            if(sums[i] > max){
                max = sums[i];
            }
        }
       
        return max;
    }
}

120. Word Ladder

思路：

1. 确认空集，开始词等于结束词的特殊情况
2. 将start string放入queue
3.  length = 1
4. queue进行操作获取当前string的所有transformation
5. 判断dict中是否存在transformation
6. 判断hash中是否已经出现过这个transformation
7. 4 && 5 都没有发生，判断是否为end。 是， 返回length
8. 过即为可能的next level string 加入queue 同时加入hash
1. 任何后出现的同一个transformation string 都是相同length 或者length + 1...
9. 循环直到queue空返回0

public class Solution {
    /*
     * @param start: a string
     * @param end: a string
     * @param dict: a set of string
     * @return: An integer
     */
    public int ladderLength(String start, String end, Set<String> dict) {
      if (dict == null) {
          return 0;
      }
     
      if (start.equals(end)) {
          return 1;
      }
     
      dict.add(start);
      dict.add(end);
     
      // HashSet检查这个word是否已经作为一个transformation出现过
      HashSet<String> hash = new HashSet<String>();
     
      Queue<String> queue = new LinkedList<String>();
      queue.offer(start);
      hash.add(start);
     
      int length = 1;
      //
      while(!queue.isEmpty()) {
          length++;
          int size = queue.size();
          for (int i = 0; i < size; i++) {
              String word = queue.poll();
              // 获得所有现在word的transformation结果
              // CE: typo getnextWords
              for (String nextWord: getNextWords(word, dict)) {
                  // 判断这个transformation出现过没有
                  if (hash.contains(nextWord)) {
                      continue;
                  }
                  if (nextWord.equals(end)) {
                      return length;
                  }
                 
                  hash.add(nextWord);
                  queue.offer(nextWord);
              }
          }
      }
      return 0;
    }
   
    // replace character of a string at given index to a given character
    // return a new string
    private String replace(String s, int index, char c) {
        // CE: typo charp
        char[] chars = s.toCharArray();
        // CE: typo
        chars[index] = c;
        return new String(chars);
    }
   
    // get connections with given word.
    // for example, given word = 'hot', dict = {'hot', 'hit', 'hog'}
    // it will return ['hit', 'hog']
    private ArrayList<String> getNextWords(String word, Set<String> dict) {
        ArrayList<String> nextWords = new ArrayList<String>();
        for (char c = 'a'; c <= 'z'; c++) {
            for (int i = 0; i < word.length(); i++) {
                if (c == word.charAt(i)) {
                    continue;
                }

                String nextWord = replace(word, i ,c);
                if (dict.contains(nextWord)) {
                    nextWords.add(nextWord);
                }
            }
        }
        return nextWords;
    }
}

18. Subsets II

public class Solution {
    /**
     * @param nums: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // write your code here
       
        List<List<Integer>> rst = new ArrayList<>();
        Arrays.sort(nums);
        List<Integer> prev = new ArrayList<>();
        helper(prev, 0, nums, rst);
        return rst;
    }
   
    private void helper(List<Integer> subset, int start, int[] nums, List<List<Integer>> rst) {
        rst.add(new ArrayList<Integer>(subset));
        for(int i = start; i < nums.length; i++) {
            if (i != start && nums[i]==nums[i-1]) {
                continue;
            }
            List<Integer> cur = new LinkedList<>(subset);
            cur.add(nums[i]);
            helper(cur, i+1, nums, rst);
            // [1,2] -> [1]  回溯
            cur.remove(cur.size() - 1);
        }
    }
   
   
   
}

17. Subsets

Given a set of distinct integers, return all possible subsets.

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets

根据第一条
ex:
S = [1, 2, 3]

1:
1
12
13
123

2:
2
23

3:
3

想法：
List<List<Integer>> res  = new List<List<Integer>()
for(int i = 0; i<S.size; i++) {
     List<Integer> prev = new ArrayList<>();
     prev.add(i);
     helper(
}

helper(List<Integer> prev, i, n, res) {
    if(i == n) {
        return;
    } else {
       
       for(int i = 0; i<S.size; i++) {
          List<Integer> cur = new ArrayList<>(prev);
          cur.add(i);
          res.add(cur);
          helper(cur, i+1, n, res)
       }
    }
}


Code（WA）

input：[1,2]

output：
[[],[1],[1,2],[2],[2,2]]


 

  public List<List<Integer>> subsets(int[] nums) {
        // write your code here
        List<List<Integer>> rst = new ArrayList<>();
        Arrays.sort(nums);
        List<Integer> prev = new ArrayList<>();
        rst.add(prev);
       
        helper(prev, 0, nums, rst);
        return rst;
    }
   
    private void helper(List<Integer> prev, int i, int[] nums, List<List<Integer>> rst) {
        if(i == nums.length) {
            return;
        } else {
            for(int k = i; k < nums.length; k++) {
                List<Integer> cur = new LinkedList<>(prev);
                cur.add(nums[k]);
                rst.add(cur);
                helper(cur, i+1, nums, rst);
               
            }
        }
造成这个问题的原因是没有回溯
当找到【1，2】开头的结果后 没有remove 2
导致要找【1，3】开头的结果就会变成找【1，2，3】开头的结果   


Answer
public List<List<Integer>> subsets(int[] nums) {
        // write your code here
        List<List<Integer>> rst = new ArrayList<>();
        Arrays.sort(nums);
        List<Integer> prev = new ArrayList<>();
        helper(prev, 0, nums, rst);
        return rst;
    }
   
    private void helper(List<Integer> subset, int start, int[] nums, List<List<Integer>> rst) {
        rst.add(new ArrayList<Integer>(subset));
        for(int i = start; i < nums.length; i++) {
            List<Integer> cur = new LinkedList<>(subset);
            cur.add(nums[i]);
            helper(cur, i+1, nums, rst);
           

// [1,2] -> [1]  回溯

            cur.remove(cur.size() - 1);
        }
    }

33. N-Queens

N-Queues
国际象棋的皇后是可以向8个方向走的
所以在同一列（1）， 同一行（2），同一条斜线（3）上是不能出现两个皇后的
因为我们在同一列（1）不会出现两个皇后
所以我们可以通过一个一位数组纪录每一列的Q在哪一行
下标（index）为第几列，值为第几行
这也是一个DFS在我们放下第一个Q后
我们需要以第一个Q的位置为依据判断下一个Q的摆放位置

Is it a Valid Queen
判断依据 即另外两个条件：

1. 不在 同一行（2）（新的Q的值（数）不会与之前数组内的值（列数）相同）
2. 不在 同一条斜线（3）（新的Q的值与列数差（斜线）不会与之前数组内的相同）

public class Solution {
    /*
     * @param n: The number of queens
     * @return: All distinct solutions
     */
    public List<List<String>> solveNQueens(int n) {
        // write your code here
        List<List<String>> res = new ArrayList<>();
       
        helper(n, 0, new int[n], res);
        return res;
    }
   
    private void helper(int n, int row, int[] columnForRow, List<List<String>> res) 
    { 
        if(row == n) 
        { 
            List<String> item = new ArrayList<>();; 
            for(int i=0;i<n;i++) 
            { 
                StringBuilder strRow = new StringBuilder(); 
                for(int j=0;j<n;j++) 
                { 
                    if(columnForRow[i]==j) 
                        strRow.append('Q'); 
                    else 
                        strRow.append('.'); 
                } 
                item.add(strRow.toString()); 
            } 
            res.add(item); 
            return; 
        } 
        for(int i=0;i<n;i++) 
        { 
            columnForRow[row] = i; 
            if(check(row,columnForRow)) 
            { 
                helper(n,row+1,columnForRow,res); 
            } 
        } 
    } 
    private boolean check(int row, int[] columnForRow) 
    { 
        for(int i=0;i<row;i++) 
        { 
            if(columnForRow[row]==columnForRow[i] || Math.abs(columnForRow[row]-columnForRow[i])==row-i) 
                return false; 
        } 
        return true; 
    } 
}

120. Word Ladder （Self， WA）

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

Thinking:
分为

1. 记录transformation的过程（记录如何变化的）
1. helper function 用来判断是否还剩一步就能变化成功，即与目标单词之差一个letter 
2. dfs
3. 如果在一次dfs中已经变化过那就可以从set去除了
2. 比较得到最短的tranformation
1. 设立rst为Integer.MAX_VALUE;

Leetcode discussion

1. It’s much faster than one-end search indeed as explained in wiki.
2. BFS isn’t equivalent to Queue. Sometimes Set is more accurate representation for nodes of level. (also handy since we need to check if we meet from two ends)
3. It’s safe to share a visited set for both ends since if they meet same string it terminates early. (vis is useful since we cannot remove word from dict due to bidirectional search)
4. It seems like if(set.add()) is a little slower than if(!contains()) then add() but it’s more concise.

 unsolved:
public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
        Set<String> reached = new HashSet<String>();
        reached.add(beginWord);
        wordDict.add(endWord);
        int distance = 1;
        while (!reached.contains(endWord)) {
            Set<String> toAdd = new HashSet<String>();
            for (String each : reached) {
                for (int i = 0; i < each.length(); i++) {
                    char[] chars = each.toCharArray();
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        chars[i] = ch;
                        String word = new String(chars);
                        if (wordDict.contains(word)) {
                            toAdd.add(word);
                            wordDict.remove(word);
                        }
                    }
                }
            }
            distance++;
            if (toAdd.size() == 0) return 0;
            reached = toAdd;
        }
        return distance;

127. Topological Sorting

Given an directed graph, a topological order of the graph nodes is defined as follow:

• For each directed edge A -> B in graph, A must before B in the order list.
• The first node in the order can be any node in the graph with no nodes direct to it.

思考：
BFS (??)
使用queue

/**
 * Definition for Directed graph.
 * class DirectedGraphNode {
 *     int label;
 *     ArrayList<DirectedGraphNode> neighbors;
 *     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
 * };
 */

public class Solution {
    /*
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */
    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        // write your code here
        if (graph == null || graph.size() == 0) {
            return graph;
        }
       
        ArrayList<DirectedGraphNode> rst = new ArrayList<>();
       
       
        // keep track of all neighbors in HashMap
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        // 找到所有被directed的点并记录被directed多少次
        for (DirectedGraphNode node : graph) {
            for (DirectedGraphNode neighbor : node.neighbors) {
                int key = neighbor.label;
                if (map.containsKey(key)) {
                    map.put(key, map.get(key) + 1);
                } else {
                    map.put(key, 1);
                }
            }
        }
       
        // find all the root which never be directed and cannot be found in map
        Queue<DirectedGraphNode> queue = new LinkedList<> ();
        for (DirectedGraphNode node : graph) {
            if (!map.containsKey(node.label)) {
                queue.offer(node);
                rst.add(node);
            }
        }
       
       
        // BFS: according the node in queue to proccess
        while (!queue.isEmpty()) {
            DirectedGraphNode node = queue.poll();
            for (DirectedGraphNode neighbor : node.neighbors) {
                int key = neighbor.label;
                map.put(key, map.get(key)-1);
                if(map.get(key) == 0) {
                    queue.offer(neighbor);
                    rst.add(neighbor);
                }
            }
        }
        return rst;
       
    }
   
}

Combination Question and DFS

Most of Combination questions connect to DFS, following structure is common:

private void dfs(int[] nums, int pos, int gap, List<Integer> list, List<List<Integer>> result) {
       
        // 一个合法的解
        if (gap == 0) {
            result.add(new ArrayList<Integer>(list));
            return;
        }
       
        for (int i = pos; i < nums.length; i++) { //扩展状态           
            // 剪枝
            if (gap < nums[i]) {
                return;
            }
           
            list.add(nums[i]); // 扩展动作
            dfs(nums, i, gap-candidates[i], list, result);
            // backtrack 撤销动作
            list.remove(list.size() - 1);
           
        }
    }

Wikipedia上的讲解是：“Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. 
One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible 
along each branch before backtracking.”

深度优先主要思想是：

1. 设置几个方法，有顺序
1. 方法： 1，2，3.....
2. 按照方法1 去执行直到方法一执行不能，尝试方法2
3. 若所有方法都不发执行，退回到上一个步骤执行方法2（因为方法1 已经执行过了）（backtracking)
4. 在执行方法的每一步中要检测是否到达目的地或目标

// recursive  

void dfs()  
{  
    // 判断是否到达终点
    if() {
        return;
    }

    // 尝试每一个可走方向（右下左上） 
    for(i=0; i<n; i++){ 
        // 判断是否可走,可走调用递归尝试下一步，不可走则尝试该点的其他方向
        if () {
            // 继续下一步  
            dfs();  
        }
    }  
}  

non-recursive
procedure DFS-iterative(G,v):
      let S be a stack
      S.push(v)
      while S is not empty
            v ← S.pop()
            if v is not labeled as discovered:
                label v as discovered
                for all edges from v to w in G.adjacentEdges(v) do
                    S.push(w)

7. Binary Tree Serialization

Thinking:

1. binary Tree 和 Stringbuilder 的联合题
2. 对Stringbuilder 和StringTokenizer的使用方法的考验

public String serialize(TreeNode root) {
        // write your code here
        StringBuilder result = new StringBuilder();
        if (root == null) return result.toString();
       
        serialHelper(root, result);
        return result.substring(0, result.length() - 1);
    }
   
    private void serialHelper(TreeNode root, StringBuilder result) {
        if (root == null) {
            result.append("#,");
        } else {
            result.append(root.val).append(",");
            serialHelper(root.left, result);
            serialHelper(root.right, result);
        }
    }

    /**
     * This method will be invoked second, the argument data is what exactly
     * you serialized at method "serialize", that means the data is not given by
     * system, it's given by your own serialize method. So the format of data is
     * designed by yourself, and deserialize it here as you serialize it in
     * "serialize" method.
     */
    public TreeNode deserialize(String data) {
        // write your code here
        if (data == null || data.length() == 0) return null;

        StringTokenizer st = new StringTokenizer(data, ",");
        return deseriaHelper(st);
    }
   
    private TreeNode deseriaHelper(StringTokenizer st) {
        if (!st.hasMoreTokens()) return null;

        String val = st.nextToken();
        if (val.equals("#")) {
            return null;
        }

        TreeNode root = new TreeNode(Integer.parseInt(val));
        root.left = deseriaHelper(st);
        root.right = deseriaHelper(st);

        return root;
    }

11. Search Range in Binary Search Tree

Thinking：

1. 简单的Traversal the tree
2. 结果要求inorder 所以 left mid right

public class Solution {
    /**
     * @param root: param root: The root of the binary search tree
     * @param k1: An integer
     * @param k2: An integer
     * @return: return: Return all keys that k1<=key<=k2 in ascending order
     */
    public List<Integer> searchRange(TreeNode root, int k1, int k2) {
        // write your code here
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        helper(root, k1, k2, result);
        return result;
       
    }
    private void helper(TreeNode root, int k1, int k2,  List<Integer> result) {
        if (root == null) {
            return;
        }
       
       
        helper(root.left, k1, k2, result);
        if (root.val >= k1 && root.val <= k2) {
            result.add(root.val);
        }
       
        helper(root.right, k1, k2, result);
    }
}

73. Construct Binary Tree from Preorder and Inorder Traversal

public class Solution {
    /**
     * @param inorder: A list of integers that inorder traversal of a tree
     * @param postorder: A list of integers that postorder traversal of a tree
     * @return: Root of a tree
     */
   
    private int findPosition(int[] arr, int start, int end, int key) {
        int i;
        for (i = start; i <= end; i++) {
            if (arr[i] == key) {
                return i;
            }
        }
        return -1;
    }
   
   
     private TreeNode myBuildTree(int[] inorder, int instart, int inend,
            int[] preorder, int prestart, int preend) {
        if (instart > inend) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[prestart]);
        // 在inorder中找到了root的位置
        int position = findPosition(inorder, instart, inend, preorder[prestart]);
       
        // 找到左子树和右子树分别为多大
        int leftSubLength = position - 1 - instart;
        int rightSubLength = inend - (position + 1) ;
       
        //  找root的left child 和right child
        //  即在preorder中root后leftSubLength长度的数组为左子树
        //  rightSubLength 长度的数组为右子树
        //  左右子树的第0为左右子树的root
        root.left = myBuildTree(inorder, instart, position - 1,
                preorder, prestart + 1, prestart + 1 + leftSubLength);
        root.right = myBuildTree(inorder, position + 1, inend,
                preorder, prestart + position - instart + 1, preend);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (inorder.length != preorder.length) {
            return null;
        }
        return myBuildTree(inorder, 0, inorder.length - 1, preorder, 0, preorder.length - 1);
    }
}

95. Validate Binary Search Tree

Thinking

1.  因为递归，所以只要思考本身就行
2. 合理的二叉树 
1. root要比left subtree中的maximum大
2. root要比right subtree中的minimum小
3. left subtree 和 right subtree 都必须是合理的二叉树（这个第一次没有想到）

通过第二点合理的二叉树，可以依此建立一个class 作为返回类型

public class ReturnType {

int min;

int max;

boolean isBST;

public ReturnType (int min, int max, boolean isBST) {

this.min = min;

this.max = max;

this.isBST = isBST;

}

}

public ReturnType dfs(TreeNode root) {

        ReturnType ret = new ReturnType(Integer.MAX_VALUE, Integer.MIN_VALUE, true);

        

        if (root == null) {

            return ret;

        }

        

        ReturnType left = dfs(root.left);

        ReturnType right = dfs(root.right);

        

        if (!left.isBST || !right.isBST) {

            ret.isBST = false;

            return ret;

        }

        

        if(root.left != null && root.val <= left.max) {

            ret.isBST = false;

            return ret;

        }

        

         if(root.right != null && root.val >= right.min) {

            ret.isBST = false;

            return ret;

        }

        

        return new ReturnType(Math.min(root.val, left.min), Math.max(root.val, right.max), true);

        

        

    }

69. Binary Tree Level Order Traversal

/*
            想到了用queue但是对 queue的使用不熟练
            LinkedList 用来实现queue方法是 poll，offer，size
       
        */
       List result = new ArrayList();
     
       if (root == null) {
           return result;
       }
     
       Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
       
        while(!queue.isEmpty()) {
            ArrayList<Integer> level = new ArrayList<>();
            int size = queue.size();
            for(int i = 0; i<size; i++) {
                TreeNode temp = queue.poll();
                level.add(temp.val);
                if(temp.left != null) {
                    queue.offer(temp.left);
                }
                if(temp.right != null) {
                    queue.offer(temp.right);
                }
            }
            result.add(level);
        }
        return result;
    }


LinkedList Method:

• poll
• offer
• size

ArrayList Method:

• add

98 Sort List

if (head == null || head.next == null) {
            return head;
        }
        
        ListNode lessDummy = new ListNode(0);
        ListNode less = lessDummy;
        ListNode greaterDummy = new ListNode(0);
        ListNode greater = greaterDummy;
        ListNode equal = head;
        ListNode curr = head.next;
        while (curr != null) {
            if (curr.val < head.val) {
                less.next = curr;
                less = less.next;
            }
            else if (curr.val > head.val) {
                greater.next = curr;
                greater = greater.next;
            }
            else { // curr.val == head.val
                equal.next = curr;
                equal = equal.next;
            }
            curr = curr.next;
        }
        less.next = null;
        greater.next = null;
        equal.next = null;
        
        lessDummy.next = sortList(lessDummy.next);
        greaterDummy.next = sortList(greaterDummy.next);
        
        ListNode dummy = lessDummy;
        curr = dummy;
        while (curr.next != null) {
            curr = curr.next;
        }
        curr.next = head;
        equal.next = greaterDummy.next;
        
        return dummy.next;