LeetCode 199 Binary Tree Right Side View

#**LeetCode 199**
---
https://leetcode.com/problems/binary-tree-right-side-view/description/

Yifeng Zeng

#Description
---
[199. Binary Tree Right Side View](https://leetcode.com/problems/binary-tree-right-side-view/description/)


#Idea Report
---

If I'm standing on the right side of a binary tree, I would see the right-most node of each level of the tree. So this becomes a problem to find the right-most node in each level of the tree. We can do a root-right-left preorder traversal and for each level we just record the first node that has been traversed. This can be achieved both using DFS or BFS.


Code
```java
public class Solution {
    // DFS
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfsHelper(res, root, 0);
        return res;
    }

    private void dfsHelper(List<Integer> res, TreeNode root, int level) {
        if (root == null) {
            return;
        }

        if (res.size() == level) {
            res.add(root.val);
        }

        dfsHelper(res, root.right, level + 1);
        dfsHelper(res, root.left, level + 1);
    }
}
```

Code
```java
public class Solution {
    // BFS
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int level = 0;

        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = q.poll();
                if (res.size() == level) {
                    res.add(cur.val);
                }
                if (cur.right != null) {
                    q.offer(cur.right);
                }
                if (cur.left != null) {
                    q.offer(cur.left);
                }
            }
            level++;
        }

        return res;
    }
}
```

#Summary
---
- Standard DFS/BFS operation in binary tree.

LeetCode 200 Number of Islands

#**LeetCode 200**
---
https://leetcode.com/problems/number-of-islands/description/

Yifeng Zeng

#Description
---
[200. Number of Islands](https://leetcode.com/problems/number-of-islands/description/)


#Idea Report
---

An island is all the connected points in the matrix. So we can treat a point as a node in a undrected graph, each pair of nodes next to each other has an edge connect to them. In this case, we can just traverse the whole matrix. Each time we find a point that is a part of island ('1'), we do a search from that point, and mark all the points to a special character so that in the next iterations we would skip them in order to get the number of the different islands. We can do both BFS or DFS.

When writing the code, we can ask if we need to maintain the original input, it we need, we can assign traversed island points to a special character and recover it before return.

Code
```java
public class Solution {

  // BFS
  public int numIslands(char[][] grid) {
      if (grid == null || grid.length == 0 || grid[0].length == 0) {
          return 0;
      }

      int rows = grid.length;
      int cols = grid[0].length;
      int count = 0;
      for (int r = 0; r < rows; r++) {
          for (int c = 0; c < cols; c++) {
              if (grid[r][c] == '1') {
                  bfsHelper(grid, r, c);
                  count++;
              }
          }
      }
      return count;
  }

  private void bfsHelper(char[][] grid, int row, int col) {
      int[] dx = {0, 0, 1, -1};
      int[] dy = {1, -1, 0, 0};
      Deque<int[]> q = new LinkedList<>();
      q.offer(new int[]{row, col});
      grid[row][col] = '0';

      while (!q.isEmpty()) {
          int[] cur = q.poll();
          for (int i = 0; i < dx.length; i++) {
              int r = cur[0] + dx[i];
              int c = cur[1] + dy[i];
              if (isValid(grid, r, c)) {
                  q.offer(new int[]{r, c});
                  grid[r][c] = '0';
              }
          }
      }
  }

  private boolean isValid(char[][] grid, int r, int c) {
      if (0 <= r && r < grid.length && 0 <= c && c < grid[0].length) {
          return grid[r][c] == '1';
      }
      return false;
  }
}
```

Code
```java
class Solution {

    // DFS
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        int rows = grid.length;
        int cols = grid[0].length;
        int count = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') {
                    dfsHelper(grid, r, c);
                    count++;
                }
            }
        }
        return count;
    }

    private void dfsHelper(char[][] grid, int row, int col) {
        if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length) {
            return;
        }
        if (grid[row][col] == '0') {
            return;
        }

        grid[row][col] = '0';
        dfsHelper(grid, row+1, col);
        dfsHelper(grid, row-1, col);
        dfsHelper(grid, row, col+1);
        dfsHelper(grid, row, col-1);
    }
}
```

#Summary
---
- Moving on a matrix can be represented as search in an undirected graph.
- Use the following array to represent the direction
  - int[] dx = {0, 0, 1, -1};
  - int[] dy = {1, -1, 0, 0};
- Use separate method isValid() to see if a move is within the boundary

LeetCode 46 Permutations

#**LeetCode 46**
---
https://leetcode.com/problems/permutations/description/

Yifeng Zeng

#Description
---
[46. Permutations](https://leetcode.com/problems/permutations/description/)


#Idea Report
---

Each time we need to select a number out from input add to a list, and recursively do the same thing until the list has all the element from the input. But how can we know which element is already selected or not? We can have an array of same length of the input, if we select one element already, we set that index to 1, so when we pick a number, we only picks ones from the index of 0s. And when the list has the same size of the input, meaning we selected all the elements from the input, we can just add this list to the final result.

Code
```java
public class Solution {

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int[] visited = new int[nums.length];
        dfsHelper(res, new ArrayList<>(), nums, visited);
        return res;
    }

    private void dfsHelper(List<List<Integer>> res,
                          List<Integer> permutation,
                          int[] nums,
                          int[] visited) {
        if (permutation.size() == nums.length) {
            res.add(new ArrayList<>(permutation));
        }
        for (int i = 0; i < nums.length; i++) {
            if (visited[i] == 0) {
                permutation.add(nums[i]);
                visited[i] = 1;
                dfsHelper(res, permutation, nums, visited);
                permutation.remove(permutation.size() - 1);
                visited[i] = 0;
            }
        }
    }
}
```

#Summary
---
- This is the standard DFS template, need to be very familiar with it.
- Deep copy.

LeetCode 505 The Maze II Accepted

#**LeetCode 505**
---
https://leetcode.com/problems/the-maze-ii/description/

Yifeng Zeng

#Description
---
[505. The Maze II](https://leetcode.com/problems/the-maze-ii/description/)


#Idea Report
---

Basically this is a search problem in a graph. The ball can move like a rook in chess. We can search for any position this ball will be, and calculate the distance from start. Then if the ball finally reach to the destination, we compare the distances and return the minimum.

Code
```java
// Time Limit Exceeded
class Solution {
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        if (maze == null || maze.length == 0 || maze[0].length == 0) {
            return -1;
        }

        int rows = maze.length;
        int cols = maze[0].length;
        int[][] visited = new int[rows][cols];
        int[] shortest = new int[1];
        shortest[0] = Integer.MAX_VALUE;

        shortestDistance(maze, start, destination, visited, 0, shortest);

        return shortest[0] == Integer.MAX_VALUE ? -1 : shortest[0];
    }

    private void shortestDistance(int[][] maze,
                                  int[] start,
                                  int[] destination,
                                  int[][] visited,
                                  int distance,
                                  int[] shortest) {
        if (start[0] == destination[0] && start[1] == destination[1]) {
            shortest[0] = Math.min(shortest[0], distance);
            return;
        }
        List<int[]> nextLocations = findNextLocations(maze, start, visited);
        for (int[] nextLocation : nextLocations) {
            if (visited[nextLocation[0]][nextLocation[1]] == 0) {
                visited[nextLocation[0]][nextLocation[1]] = 1;
                shortestDistance(maze, nextLocation, destination, visited,
                    distance + calculateDistance(start, nextLocation),
                    shortest);
                visited[nextLocation[0]][nextLocation[1]] = 0;
            }

        }
    }


    private List<int[]> findNextLocations(int[][] maze, int[] start,
                                          int[][] visited) {
        List<int[]> nextLocations = new ArrayList<>();
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};

        for (int i = 0; i < dx.length; i++) {
            int[] nextLocation =
                findNextLocation(maze, start[0], start[1], dx[i], dy[i]);
            nextLocations.add(nextLocation);
        }
        return nextLocations;
    }


    private int[] findNextLocation(int[][] maze, int x, int y, int dx, int dy) {
        int[] nextLocation = new int[]{x, y};

        while (isValid(maze, x, y)) {
            nextLocation[0] = x;
            nextLocation[1] = y;
            x += dx;
            y += dy;
        }
        return nextLocation;
    }


    private boolean isValid(int[][] maze, int x, int y) {
        if (0 <= x && x < maze.length && 0 <= y && y < maze[0].length) {
            return maze[x][y] == 0;
        }
        return false;
    }


    private int calculateDistance(int[] start, int[] end) {
        if (start[0] == end[0]) {
            return Math.abs(start[1] - end[1]);
        }
        return Math.abs(start[0] - end[0]);
    }
}
```

The above DFS code exceeds the time limit, because we search all the posibilities. But some of the posibilities might not need to be searched because the ball might travel to a wrong direction. We use a distances[][] matrix to save the minimum distance from start point for each possible location. If we search to a certain location but the current distance is larger than the minimum distance in the record (in distances[][]), we just stop the meaningless searching because that path is no longer the optimal path.

Code
```java
// AC
class Solution {
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        if (maze == null || maze.length == 0 || maze[0].length == 0) {
            return -1;
        }

        int rows = maze.length;
        int cols = maze[0].length;
        int[][] distances = new int[rows][cols];
        for (int[] dist : distances) {
            Arrays.fill(dist, Integer.MAX_VALUE);
        }
        distances[start[0]][start[1]] = 0;

        Deque<int[]> q = new LinkedList<>();
        q.offer(start);

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            List<int[]> nextLocations = findNextLocations(maze, cur);
            for (int[] nextLocation : nextLocations) {
                int distance = calculateDistance(cur, nextLocation)
                    + distances[cur[0]][cur[1]];
                if (distances[nextLocation[0]][nextLocation[1]] > distance) {
                    distances[nextLocation[0]][nextLocation[1]] = distance;
                    q.offer(nextLocation);
                }
            }
        }

        return distances[destination[0]][destination[1]] == Integer.MAX_VALUE ?
            -1 : distances[destination[0]][destination[1]];
    }

    // reuse the following methods from DFS
    private List<int[]> findNextLocations(int[][] maze, int[] start) {
        List<int[]> nextLocations = new ArrayList<>();
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};

        for (int i = 0; i < dx.length; i++) {
            int[] nextLocation =
                findNextLocation(maze, start[0], start[1], dx[i], dy[i]);
            nextLocations.add(nextLocation);
        }
        return nextLocations;
    }


    private int[] findNextLocation(int[][] maze, int x, int y, int dx, int dy) {
        int[] nextLocation = new int[]{x, y};

        while (isValid(maze, x, y)) {
            nextLocation[0] = x;
            nextLocation[1] = y;
            x += dx;
            y += dy;
        }
        return nextLocation;
    }


    private boolean isValid(int[][] maze, int x, int y) {
        if (0 <= x && x < maze.length && 0 <= y && y < maze[0].length) {
            return maze[x][y] == 0;
        }
        return false;
    }


    private int calculateDistance(int[] start, int[] end) {
        if (start[0] == end[0]) {
            return Math.abs(start[1] - end[1]);
        }
        return Math.abs(start[0] - end[0]);
    }

}

```
#Summary
---
- Record the temporary optimal when searching a global optimal is a way to speed up (memorize search).
- Use different function to modularize the program is a good practice.
- Note:
  - Use this for four direction movement:
    - int[] dx = {0, 0, 1, -1};
    - int[] dy = {1, -1, 0, 0};


#Follow up
---
In the DFS method, I used a distances[][] to memorize the search and change the int[] to class Point and finally got accepted.

Code
```java
class Solution {
    // DFS AC
    class Point{
        int x;
        int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        if (maze == null || maze.length == 0 || maze[0].length == 0) {
            return -1;
        }

        int rows = maze.length;
        int cols = maze[0].length;
        int[][] distances = new int[rows][cols];
        for (int[] dist : distances) {
            Arrays.fill(dist, Integer.MAX_VALUE);
        }
        distances[start[0]][start[1]] = 0;

        shortestDistance(maze, new Point(start[0], start[1]), distances);

        return distances[destination[0]][destination[1]] == Integer.MAX_VALUE ?
            -1 : distances[destination[0]][destination[1]];
    }

    private void shortestDistance(int[][] maze,
                                  Point cur,
                                  int[][] distances) {
        List<Point> nextLocations = findNextLocations(maze, cur);
        for (Point nextLocation : nextLocations) {
            int nextDistance = distances[cur.x][cur.y]
                               + calculateDistance(cur, nextLocation);
            if (distances[nextLocation.x][nextLocation.y] > nextDistance) {
                distances[nextLocation.x][nextLocation.y] = nextDistance;
                shortestDistance(maze, nextLocation, distances);
            }
        }
    }


    private List<Point> findNextLocations(int[][] maze, Point cur) {
        List<Point> nextLocations = new ArrayList<>();
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};

        for (int i = 0; i < dx.length; i++) {
            Point nextLocation =
                findNextLocation(maze, cur.x, cur.y, dx[i], dy[i]);
            nextLocations.add(nextLocation);
        }
        return nextLocations;
    }


    private Point findNextLocation(int[][] maze, int x, int y, int dx, int dy) {
        Point nextLocation = new Point(x, y);

        while (isValid(maze, x, y)) {
            nextLocation.x = x;
            nextLocation.y = y;
            x += dx;
            y += dy;
        }
        return nextLocation;
    }


    private boolean isValid(int[][] maze, int x, int y) {
        if (0 <= x && x < maze.length && 0 <= y && y < maze[0].length) {
            return maze[x][y] == 0;
        }
        return false;
    }


    private int calculateDistance(Point start, Point end) {
        if (start.x == end.x) {
            return Math.abs(start.y - end.y);
        }
        return Math.abs(start.x - end.x);
    }
}
```

#Follow up
---
The same DFS code but using int[] instead of Point class, I thought I got time limit exceeded, but got accepted when I submit again.

Code
```java
class Solution {

    // DFS AC
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        if (maze == null || maze.length == 0 || maze[0].length == 0) {
            return -1;
        }

        int rows = maze.length;
        int cols = maze[0].length;
        int[][] distances = new int[rows][cols];
        for (int[] dist : distances) {
            Arrays.fill(dist, Integer.MAX_VALUE);
        }
        distances[start[0]][start[1]] = 0;

        shortestDistance(maze, start, distances);

        return distances[destination[0]][destination[1]] == Integer.MAX_VALUE ?
            -1 : distances[destination[0]][destination[1]];
    }

    private void shortestDistance(int[][] maze,
                                  int[] cur,
                                  int[][] distances) {
        List<int[]> nextLocations = findNextLocations(maze, cur);
        for (int[] nextLocation : nextLocations) {
            int nextDistance = distances[cur[0]][cur[1]]
                + calculateDistance(cur, nextLocation);
            if (distances[nextLocation[0]][nextLocation[1]] > nextDistance) {
                distances[nextLocation[0]][nextLocation[1]] = nextDistance;
                shortestDistance(maze, nextLocation, distances);
            }
        }
    }


    private List<int[]> findNextLocations(int[][] maze, int[] start) {
        List<int[]> nextLocations = new ArrayList<>();
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};

        for (int i = 0; i < dx.length; i++) {
            int[] nextLocation =
                findNextLocation(maze, start[0], start[1], dx[i], dy[i]);
            nextLocations.add(nextLocation);
        }
        return nextLocations;
    }

    private int[] findNextLocation(int[][] maze, int x, int y, int dx, int dy) {
        int[] nextLocation = new int[]{x, y};

        while (isValid(maze, x, y)) {
            nextLocation[0] = x;
            nextLocation[1] = y;
            x += dx;
            y += dy;
        }
        return nextLocation;
    }

    private boolean isValid(int[][] maze, int x, int y) {
        if (0 <= x && x < maze.length && 0 <= y && y < maze[0].length) {
            return maze[x][y] == 0;
        }
        return false;
    }

    private int calculateDistance(int[] start, int[] end) {
        if (start[0] == end[0]) {
            return Math.abs(start[1] - end[1]);
        }
        return Math.abs(start[0] - end[0]);
    }
}
```

LeetCode 505. The Maze II Time Limit Exceeded 27 / 78 test cases passed.

Code
```java
// Time Limit Exceeded
class Solution {
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        if (maze == null || maze.length == 0 || maze[0].length == 0) {
            return -1;
        }
     
        int rows = maze.length;
        int cols = maze[0].length;
        int[][] visited = new int[rows][cols];
        int[] shortest = new int[1];
        shortest[0] = Integer.MAX_VALUE;
     
        shortestDistance(maze, start, destination, visited, 0, shortest);
     
        return shortest[0] == Integer.MAX_VALUE ? -1 : shortest[0];
    }
 
    private void shortestDistance(int[][] maze,
                                  int[] start,
                                  int[] destination,
                                  int[][] visited,
                                  int distance,
                                  int[] shortest) {
        if (start[0] == destination[0] && start[1] == destination[1]) {
            shortest[0] = Math.min(shortest[0], distance);
            return;
        }
        List<int[]> nextLocations = findNextLocations(maze, start, visited);
        for (int[] nextLocation : nextLocations) {
            if (visited[nextLocation[0]][nextLocation[1]] == 0) {
                visited[nextLocation[0]][nextLocation[1]] = 1;
                shortestDistance(maze, nextLocation, destination, visited,
                                 distance + calculateDistance(start, nextLocation), shortest);
                visited[nextLocation[0]][nextLocation[1]] = 0;
            }
         
        }
    }
 
 
    private List<int[]> findNextLocations(int[][] maze, int[] start, int[][] visited) {
        List<int[]> nextLocations = new ArrayList<>();
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
     
        for (int i = 0; i < dx.length; i++) {
            int[] nextLocation = findNextLocation(maze, start[0], start[1], dx[i], dy[i]);
            nextLocations.add(nextLocation);
        }
        return nextLocations;
    }
 
 
    private int[] findNextLocation(int[][] maze, int x, int y, int dx, int dy) {
        int[] nextLocation = new int[]{x, y};
     
        while (isValid(maze, x, y)) {
            nextLocation[0] = x;
            nextLocation[1] = y;
            x += dx;
            y += dy;
        }
        return nextLocation;
    }
 
 
    private boolean isValid(int[][] maze, int x, int y) {
        if (0 <= x && x < maze.length && 0 <= y && y < maze[0].length) {
            return maze[x][y] == 0;
        }
        return false;
    }
 
 
    private int calculateDistance(int[] start, int[] end) {
        if (start[0] == end[0]) {
            return Math.abs(start[1] - end[1]);
        }
        return Math.abs(start[0] - end[0]);
    }
}
```

LeetCode 210 Course Schedule II

#**LeetCode 210**
---
https://leetcode.com/problems/course-schedule-ii/description/

Yifeng Zeng

#Description
---
[210. Course Schedule II](https://leetcode.com/problems/course-schedule-ii/description/)


#Idea Report
---

The first step is to find all the courses that has no prerequisites, these courses are the starting point. After finishing all the staring point, there must be some courses which prerequisites are these starting point, so then we can take those classes because we hava already finished their prerequisites. And starting from there we can take next step. So we can draw something like course X point to course Y then point to course Z. This is actually a directed graph each course is a node, and a directed graph has a very important propetry which is indegree, meaning how mainly nodes goes into the current node. So our starting point are the nodes with no indegrees which are the courses with no prerequisites. We then traverse the nodes with indegree == 0, and put them into a result array. Also when we traversed a node, we need to decrese the indegree of its neighbor by one, because we have already take the class meaning we finised one of the prerequisites of the neighbor class. So when the neighbor class's indegree becomes one, we know that that class can now be taken.


Code
```java
public class Solution {

    public int[] findOrder(int n, int[][] pre) {
        List<Integer>[] neis = new List[n];
        for (int i = 0; i < n; i++) {
            neis[i] = new ArrayList<>();
        }

        int[] indegree = new int[n];
        for (int[] p : pre) {
            indegree[p[0]]++;
            neis[p[1]].add(p[0]);
        }

        Deque<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                q.offer(i);
            }
        }

        int[] res = new int[n];
        int index = 0;
        while (!q.isEmpty()) {
            int cur = q.poll();
            res[index++] = cur;
            for (int nei : neis[cur]) {
                indegree[nei]--;
                if (indegree[nei] == 0) {
                    q.offer(nei);
                }
            }
        }

        return index == n ? res : new int[0];
    }
}
```

#Summary
---
- Node-to-node reppresentation can be convertd to a directed graph.
- Topological sorting.
- List<Integer>[] neis = new List[n]; is the new thing that I learned.

LeetCode 692 Top K Frequent Words

#**LeetCode 692**
---
https://leetcode.com/problems/top-k-frequent-words/description/

Yifeng Zeng

#题目描述
---
[692. Top K Frequent Words](https://leetcode.com/problems/top-k-frequent-words/description/)


#思路报告
---

We have an unsorted array of words, and we want to find the top K frequent words, the first thing that I can think of is to have a sort of container or data structure to hold the most frequent elements (String). And once a new String comes, we compare the least frequent element in the container to this new String, if this new String is less frequent, we do nothing, otherwise, we remove the least frequent element out of the container and add this new String into that container. To find the least frequent or the smallest number in a container in O(1) time, we can think of a minHeap. So we maintain a size K minHeap to get the top K frequent words.

During coding, we can discuss one thing that needs to be taken care of: Every time we want to peek the least frequent element in the heap, so this heap should be a min heap of frequency. But what if the frequency is the same? For example we have a X 2, b X 2 and c X 2 and k = 2, we want to keep a and b, and ditch c. So with the same frequency, we want to keep a smaller string in lexicographical order. So use str2.CompareTo(str1) when frequency is the same. Another thing that needs to be careful is that it is a minHeap so least frequent word will be polled out first, so after polling out all the strings from the min heap, we want to reverse the list so that the most frequent string is at the beginning.

代码如下：
```java
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }

        Queue<String> pq = new PriorityQueue<>(
            (str1, str2) -> (map.get(str1) == map.get(str2) ? str2.compareTo(str1) : map.get(str1) - map.get(str2)));

        for (String key : map.keySet()) {
            pq.offer(key);
            if (pq.size() > k) {
                pq.poll();
            }
        }

        List<String> res = new ArrayList<>();
        while (!pq.isEmpty()) {
            res.add(pq.poll());
        }
        Collections.reverse(res);

        return res;
    }
}
```

#套路总结
---
- Consider using a heap when dealing with "top K" question.
- map.getOrDefault(word, 0) + 1 is a new thing that I learned.
- Lambda expression is a new thing that I learned.
- Becareful about the String order when frequency is the same.

LeetCode 124. Binary Tree Maximum Path Sum

LeetCode 124

https://leetcode.com/problems/binary-tree-maximum-path-sum/description/

Yifeng Zeng

Description

124. Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example: Given the below binary tree,

       1
      / \
     2   3

Return 6.

Idea Report

The problem explicitly says:

"The path must contain at least one node and does not need to go through the root."

So this is a child-to-parent-to-child path sum. So we can split this path sum into three parts. A parent-to-child path sum from left, the root value itself, and a parent-to-child path sum from right. So we traverse the whole tree, for each root (parent), we need to compare this path's sum to the global maximum. Since we need the left side and right side of the parent-to-child path sum, we can use bottom up method.

When writing the code, we can discuss the corner cases: if left/right side path sum is less than 0, we need carefully compare all kinds of the situation. Another trick I learned in the class is to use int[] max; instead of the global variable.

Code:

class Solution {
  // AC
  public int maxPathSum(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int[] max = new int[1];
    max[0] = root.val;
    helper(root, max);
    return max[0];
  }

  private int helper(TreeNode root, int[] max) {
    if (root == null) {
        return 0;
    }

    int left = helper(root.left, max);
    int right = helper(root.right, max);
    int temp = Math.max(root.val, Math.max(left + root.val, right + root.val));
    max[0] = Math.max(max[0], Math.max(temp, left + right + root.val));
    return temp;
  }
}

Summary

• If we need information from left/right child and do not need pass any parent information down to children, we can just use bottom up method.
• Use int[] max = new int[1]; instead of a global variable.

LeetCode 543 Diameter of Binary Tree

#**LeetCode 543**
---
https://leetcode.com/problems/diameter-of-binary-tree/description/

Yifeng Zeng

#题目描述
---
[543. Diameter of Binary Tree](https://leetcode.com/problems/diameter-of-binary-tree/description/)


#思路报告
---

(This is similar with LC124)

This is a leaf-to-parent-to-leaf path length. So we can split this path into two parts. A leftleaf-to-parent and rightleaf-to-parent length. For any parent node, we compare the global maximum to left+right. And we choose a longer length between left and right plus 1 (current parent length) to return so that the upper layer of recursion can get the longest path.

代码如下：
```java
public int diameterOfBinaryTree(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int[] max = new int[1];
    diameterOfBinaryTree(root, max);
    return max[0];
}

private int diameterOfBinaryTree(TreeNode root, int[] max) {
    if (root == null) {
        return 0;
    }

    int left = diameterOfBinaryTree(root.left, max);
    int right = diameterOfBinaryTree(root.right, max);
    max[0] = Math.max(max[0], left + right);
    return Math.max(left, right) + 1;
}
```

#套路总结
---
- If we need information from left/right child and do not need pass any parent information down to children, we can just use bottom up method.
- Use int[] max = new int[1]; instead of a global variable.

LeetCode 222 Count Complete Tree Nodes

#**LeetCode 222**
---
https://leetcode.com/problems/count-complete-tree-nodes/description/

Yifeng Zeng

#题目描述
---
[222. Count Complete Tree Nodes](https://leetcode.com/problems/count-complete-tree-nodes/description/)

#思路报告
---

The primitive idea is to traverse the whole tree with a counter. When a node is traversed we increase the counter. We can use any traverse method.

代码如下：
```java
public int countNodes(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int count = 0;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode cur = stack.pop();
        count++;
        if (cur.right != null) {
            stack.push(cur.right);
        }
        if (cur.left != null) {
            stack.push(cur.left);
        }
    }

    return count;
}
```

We can traverse any tree to count the number of nodes with O(n) time. So we did not leverage the property of the complete tree. So there must be something we can improve. We know that for a complete tree node root, the left or right child has to be a perfect tree or both has to be. For a perfect tree, we can know the its number of nodes buy using H² - 1, where H is the height of the root, and we can get the H in O(H) time. So now we split the problem into some subproblem. Find the H of root.left and root.right, if they are the same height, root.left is a perfect tree and root.right is a complete tree, we can calculate the number of nodes of root.left by using H² - 1, plus the root itself. And recursively find the number of nodes of root.right. If the H of root.left and root.right is not the same, then root.right is a perfect tree, and root.left is a sub complete tree. We can do another recursive call to get the final result. So the time complexity is O(H²) where H = logn.

Code:
```java
public int countNodes(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int left = findH(root.left);
    int right = findH(root.right);

    if (left == right) {
        return (1 << left) + countNodes(root.right);
    }

    return (1 << right) + countNodes(root.left);
}

private int findH(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int h = 1;
    while (root.left != null) {
        root = root.left;
        h++;
    }
    return h;
}
```

#套路总结
---
- When use a primitive idea, but without leveraging some property of the input, there might be a way to improve.
- Use 1 << H to get 2^H.
- Java运算符优先级有一个坑：

I used this first:

```java
1 << left + countNodes(root.right);
```
Only to find out that '+' has higher priority of '<<' so I should the following:
```java
(1 << left) + countNodes(root.right);
```

LeetCode 285 Inorder Successor in BST

#**LeetCode285**
---
https://leetcode.com/problems/inorder-successor-in-bst
http://lintcode.com/en/problem/inorder-successor-in-binary-search-tree/

Yifeng Zeng

#题目描述
---
Inorder Successor in BST

#思路报告
---

When I got this question, the first idea I have is that we can do an inorder traversal of this tree, when travered to the key node, mark a flag and return the next node that we traversed, O(n) time.

代码如下：
```java
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    if (root == null) {
        return root;
    }

    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    TreeNode res = null;
    boolean found = false;

    while (!stack.isEmpty() || cur != null) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();

        if (found) {
            return cur;
        }
        if (cur == p) {
            found = true;
        }

        cur = cur.right;
    }

    return res;
}
```

We can do inorder traversal for any tree, so we didn't leverage the property of the BST. So I can compare the root.val to p.val. If root.val < p.val then we can throw away all the children of root.left so look in root.right (do it recursively). Otherwise if root.val > p.val then we can throw away all the children of root.right, so look in root.left (do it recursively) or it is this root. If root.val == p.val, we just return the smallest node in subtree root.right. In this case, we throw away half of the candidates every time, so this is O(logn) time.
(So from a couple of feedback from my last homeworks, I guess I'm not supposed to discuss the corner cases at begining. So should I discuss the corner case when I write the code?)

Code:
```java
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    if (root == null) {
        return null;
    }

    if (root.val > p.val) {
        TreeNode left = inorderSuccessor(root.left, p);
        return left == null ? root : left;
    } else if (root.val < p.val) {
        return inorderSuccessor(root.right, p);
    }
    if (root.right == null) {
        return null;
    }
    root = root.right;
    while (root.left != null) {
        root = root.left;
    }
    return root;
}
```

#套路总结
---
- I forgot root.val > p.val, root may be the result.
- Split one big problem into a sequence of sub-prolem may do the trick.
- 通过这个题我发现其实有些时候做不出一道题最根本的原因还是思路好象不对，想到了分左边和分右边，但是没有考虑好具体root.val > p.val时其实root本身就是一个candidate。听老师讲了之后有种顿悟的感觉，思路清晰了，代码很容易就码出来了。

LeetCode 33 Search in Rotated Sorted Array

#**LeetCode33**
---
https://leetcode.com/problems/search-in-rotated-sorted-array/description/

Yifeng Zeng

#题目描述
---
Search in Rotated Sorted Array

#思路报告
---

The primitive idea is to traverse the array to see if target is in it which is O(n) time. If we want to do better we may want to consider throw away half of the impossible part of the array, which would be a binary search. Since the array is rotated, we can split it into two halves by where the retation starts. So it can be split by the last number of the array. One half is larger than the last number, the other half is smaller than the last number. If mid lays on the upper half, then if target lays between start and mid, throw the second half, end = mid, otherwise throw the first half, start = mid. If mid lays on the lower half, then if target lays between mid and end, throw the first half, start = mid, otherwise throw the second half, end = mid.

代码如下：
```java
public int search(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return -1;
    }

    int start = 0;
    int end = nums.length - 1;
    int last = nums[end];

    while (start + 1 < end) {
        int mid = (end - start) / 2 + start;
        if (nums[mid] > last) {
            if (nums[start] <= target && target <= nums[mid]) {
                end = mid;
            } else {
                start = mid;
            }
        } else {
            if (nums[mid] <= target && target <= nums[end]) {
                start = mid;
            } else {
                end = mid;
            }
        }
    }

    if (nums[start] == target) {
        return start;
    }
    if (nums[end] == target) {
        return end;
    }
    return -1;
}
```


#套路总结
---
- 把mid的位置分成多个section分类讨论

LeetCode 102 Binary Tree Level Order Traversal

#**LeetCode102**
---
https://leetcode.com/problems/binary-tree-level-order-traversal/description/

Yifeng Zeng

#题目描述
---
Binary Tree Level Order Traversal

#思路报告
---

We want to traverse the tree level by level. When traverse the first level, we want to store the next level. What type of data structure can achive that the first next-level-child stored first and come out first. That is a queue. So when we traverse the nodes in this level, we want to put the left/right child of current node into queue so that we can traverse later. The solution would be using a bfs of the root.

代码如下：
```java
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) {
        return res;
    }

    Deque<TreeNode> q = new LinkedList<>();
    q.offer(root);

    while (!q.isEmpty()) {
        int size = q.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode cur = q.poll();
            level.add(cur.val);
            if (cur.left != null) {
                q.offer(cur.left);
            }
            if (cur.right != null) {
                q.offer(cur.right);
            }
        }
        res.add(level);
    }

    return res;
}
```


#套路总结
---
- Looking for the order of the nodes that has been traversed, from left to right, and in next level we want to traverse left child to right child, so we want to use FIFO data structure queue to save the next level nodes that needs to be traversed.

LeetCode 450 Delete Node in a BST

#**LeetCode450**
---
https://leetcode.com/problems/delete-node-in-a-bst/description/

Yifeng Zeng

#题目描述
---
Delete Node in a BST

#思路报告
---

The problem can be separate into 4 sub problems. Step 1, find the node that needs to be removed (node.val == key); Step 2, from the left children of this node, find the one with the largest value, which is the one one the right most of the left children (TreeNode remove); Step 3, left node.val = remove.val; Step 4, recursively remove that remove node from node.left (deleteNode(node.left, remove.val);)

代码如下：
```java
public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) {
        return root;
    }
    // if (root.left == null && root.right == null && root.val == key) {
    //     return null;
    // }
    TreeNode node = root;
    if (node.val < key) {
        // deleteNode(node.right, key); // 坑
        node.right = deleteNode(node.right, key);
    } else if (node.val > key) {
        // deleteNode(node.left, key); // 坑
        node.left = deleteNode(node.left, key);
    } else if (node.val == key) {
        if (node.left == null) {
            node = node.right;
        } else {
            TreeNode remove = node.left;
            while (remove.right != null) {
                remove = remove.right;
            }
            node.val = remove.val;
            // deleteNode(node.left, remove.val); // 坑
            node.left = deleteNode(node.left, remove.val);
        }
    }
    // return root;
    return node;
}
```


#套路总结
---
- Sometime change the node.val is better than change the node.left, node.right pointer.
- Dividing a big problem into a sequence of sub problems is a very impoartant idea.

LeetCode 145 Binary Tree Postorder Traversal

#**LeetCode145**
---
https://leetcode.com/problems/binary-tree-postorder-traversal/description/

Yifeng Zeng

#题目描述
---
Binary Tree Postorder Traversal

#思路报告
---

Firstly we want to clearify the the post order is left-right-root order. Then I can provide a very simple recursive version but point out that the call stack may overflow if the tree is large.

Code:
```java
class Solution {

    List<Integer> res;
    public List<Integer> postorderTraversal(TreeNode root) {
        res = new ArrayList<>();
        helper(root);
        return res;
    }

    private void helper(TreeNode root) {
        if (root == null) {
            return;
        }
        helper(root.left);
        helper(root.right);
        res.add(root.val);
    }
}
```

Another recursive approach is that we think left child has all the list of integers ready (leftList), and right child has all the list of integers ready (rightList). We can append leftList + rightList + root.val to get the final result.

Code:
```java
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) {
        return res;
    }

    List<Integer> leftList = postorderTraversal(root.left);
    List<Integer> rightList = postorderTraversal(root.right);

    res.addAll(leftList);
    res.addAll(rightList);
    res.add(root.val);

    return res;
}
```

Since we talked about the stack overflow, we might want to discuss a non-recursive version. Basically we just use a stack to simulate the call stack. I will talk about Qinyuan's general version later. What I previously did is that, the order is left-right-root, and I can't think of a good way to do it, so can I try a reverse version root-right-left? The root-right-left is actually like a pre-order traversal but the right child comes at firt before the left child. So I can solve this problem by doing a pre order traversal (root-right-left) and then reverse the whole list to get the result.

Code:
```java
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) {
        return res;
    }

    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode cur = stack.pop();
        res.add(cur.val);
        if (cur.left != null) {
            stack.push(cur.left);
        }
        if (cur.right != null) {
            stack.push(cur.right);
        }
    }

    Collections.reverse(res);
    return res;
}
```

The last version was introduced by Qinyuan and I think it is a very elegent solution. When we visit to a node, we actually need to do three sub problem, 1) visit left child, 2) visit right child, 3) print current node. So for a node we have two operations visit and print. Each time the node is actually visited, we change it to the print state. For example, we have [1,2,3], if we visit root 1, we don't want to print it right now, instead we set its state to print, then next time we see node 1 and it's on print state, we print or add to the result list. Then we handle node 2 and 3 and so on.

Code:
```java
class Pair {
    TreeNode node;
    boolean print;
    public Pair(TreeNode node, boolean print) {
        this.node = node;
        this.print = print;
    }
}

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) {
        return res;
    }

    Deque<Pair> stack = new ArrayDeque<>();
    stack.push(new Pair(root, false));

    while (!stack.isEmpty()) {
        Pair cur = stack.pop();
        if (cur.node == null) {
            continue;
        }
        if (cur.print) {
            res.add(cur.node.val);
        } else {
            stack.push(new Pair(cur.node, true));
            stack.push(new Pair(cur.node.right, false));
            stack.push(new Pair(cur.node.left, false));
        }
    }

    return res;
}
```

---
- Divid and conquer is a very common method to solve a binary tree question.
- Dividing a big problem into a sequence of sub problems is a very impoartant idea.

LeetCode 98 Validate Binary Search Tree

#**LeetCode98**
---
https://leetcode.com/problems/validate-binary-search-tree/description/

Yifeng Zeng

#题目描述
---
Validate Binary Search Tree

#思路报告
---

The first thing is to clarify the defination of the BST input. The BST has a very important property which is that the in-order traversal of a BST is a non-decreasing sequence or a increasing sequence (discuss this with the interviewer, LC uses increasing sequence). So the primitive idea is to do an in-order traversal of this TreeNode, and find if the current element is smaller than the previous element. If it is, then it is not a BST, otherwise it is.

The non-recursive code that I previous recite is this:

代码如下：
```java
public boolean isValidBST(TreeNode root) {
    if (root == null) {
        return true;
    }
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    TreeNode prev = null;
    Boolean isFirst = true;

    while (!stack.isEmpty() || cur != null) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        if (isFirst) {
            prev = cur;
            isFirst = false;
        } else {
            if (cur.val <= prev.val) {
                return false;
            }
            prev = cur;
        }
        cur = cur.right;
    }

    return true;
}
```

From one of Qinyuan's lecture, the non-recursive code can be something like this, and the order can be any of pre/in/post-order. More details will be explained in the report of LC145 Binary Tree Postorder Traversal.

Code:
```java
class Pair {
    TreeNode node;
    boolean print;
    public Pair(TreeNode node, boolean print) {
        this.node = node;
        this.print = print;
    }
}

public boolean isValidBST(TreeNode root) {
    if (root == null) {
        return true;
    }

    Deque<Pair> stack = new ArrayDeque<>();
    stack.push(new Pair(root, false));
    boolean isFirst = true;
    TreeNode prev = null;

    while (!stack.isEmpty()) {
        Pair cur = stack.pop();
        if (cur.node == null) {
            continue;
        }

        if (cur.print) {
            if (isFirst) {
                isFirst = false;
            } else {
                if (cur.node.val <= prev.val) {
                    return false;
                }
            }
            prev = cur.node;
        } else {
            stack.push(new Pair(cur.node.right, false));
            stack.push(new Pair(cur.node, true));
            stack.push(new Pair(cur.node.left, false));
        }
    }

    return true;
}
```
We can also solve it without traversal. The defination is that all the left children has smaller values than the root value, all the right children has larger values than the root value and both left and right child is also a BST. Then for the current root, I can just see if the largest number in all the left children is smaller than the root value and see if the smallest number in all the right children is larger than the root value. So we can use divid and conquer. We need to see the smallest and largest number in the root's children so we might need a wrapper for return.

Code:
```java
class ReturnType {
    long max;
    long min;
    boolean isValid;
    public ReturnType(long max, long min, boolean isValid) {
        this.max = max;
        this.min = min;
        this.isValid = isValid;
    }
}

public boolean isValidBST(TreeNode root) {
    return helper(root).isValid;
}

private ReturnType helper(TreeNode root) {
    ReturnType res = new ReturnType(Long.MIN_VALUE, Long.MAX_VALUE, true);
    if (root == null) {
        return res;
    }

    res.min = root.val;
    res.max = root.val;

    ReturnType left = helper(root.left);
    ReturnType right = helper(root.right);

    res.isValid = left.isValid && right.isValid && left.max < root.val && root.val < right.min;

    res.min = Math.min(res.min, left.min);
    res.min = Math.min(res.min, right.min);
    res.max = Math.max(res.max, left.max);
    res.max = Math.max(res.max, right.max);

    return res;
}
```

#套路总结
---
- When starting to code, ask if root == null is true or false.
- The BST has a very important property which is that the in-order traversal of a BST is a non-decreasing sequence or a increasing sequence (LC uses increasing sequence).

LeetCode 16 3Sum Closest

#**LeetCode16**
---
https://leetcode.com/problems/3sum-closest/description/

Yifeng Zeng

#题目描述
---
3Sum Closest

#思路报告
---

LC167. Two Sum II - Input array is sorted的思路，左右两个指针，左右之和大于target，那么右边往左移使得sum变小，左右之和小于target，那么左边往右移使得sum变大。本题可以借鉴LC167的思路，3sum无非就是固定一个element，另外两个element像LC167那样移动去找target或者找closest target。那么我们先对数组排序，然后从左往右固定nums[i]，那么其实就是在i后面找最接近target - nums[i]的two sum。也是大于target - nums[i]时，右边往左移使sum变小，小于target - nums[i]时，左边往右移使sum变大。取绝对值来保存different最小时的nums[i]， nums[left], nums[right]的sum。

代码如下：
```java
public int threeSumClosest(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        throw new IllegalArgumentException("Invalid input");
    }

    Arrays.sort(nums);
    int diff = Integer.MAX_VALUE;
    int res = Integer.MAX_VALUE;
    for (int i = 0; i < nums.length - 2; i++) {
        int t = target - nums[i];
        int left = i + 1;
        int right = nums.length - 1;
        while (left < right) {
            int sum = nums[left] + nums[right] - t;
            if (Math.abs(sum) < diff) {
                diff = Math.abs(sum);
                res = sum + target;
            }
            if (sum > 0) {
                right--;
            } else {
                left++;
            }
        }
    }
    return res;
}
```


#套路总结
---
- 数组未排序没有好办法解的情况下可以考虑先排序。
- 多个数组合的情况可以考虑固定其中一个。

LeetCode 82 Remove Duplicates from Sorted List II

#**LeetCode82**
---
https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/

Yifeng Zeng

#题目描述
---
Remove Duplicates from Sorted List II

#思路报告
---

因为是sorted linked list，而且有重复要删除重复数字的所有node,那么意味着我们需要一个prev node来记录重复数字之前的那个node。而且第一个node就可能重复，所以我们需要一个dummy node来辅助。那么prev从dummy开始，用一前一后slow fast两个指针，只要slow fast的值相等那么fast向后移动直到不等，那么prev.next = fast就可以把所有重复的node remove掉了。如果slow fast都不相等，那么prev slow fast同时往后移一位。

代码如下：
```java
public ListNode deleteDuplicates(ListNode head) {
    if (head == null) {
        return head;
    }

    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prev = dummy;
    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null) {
        while (fast != null && fast.val == slow.val) {
            fast = fast.next;
        }

        if (slow.next == fast) {
            prev = slow;
            slow = fast;
        } else if (slow.next != fast) {
            prev.next = fast;
            slow = fast;
        }
    }

    return dummy.next;
}
```


#套路总结
---
- 改变原list的话要借助dummy node。
- 在singly linked list里面remove掉某些node的话，需要prev。

LeetCode 57 Insert Interval

#**LeetCode57**
---
https://leetcode.com/problems/insert-interval/description/

Yifeng Zeng

#题目描述
---
Insert Interval

#思路报告
---

因为intervals已经排了序了，所以我们只需要把newInterval的start和end在这些intervals里面对应的位置找到就行了。由于是从小到大排序的，我们先看newInterval.start，我们遍历intervals，找到某一个intervals.get(i)，当i.end < newInterval.start是我们把直接放到result里面，因为不会跟newInterval有overlap。这时我们有了第一个newInterval.start < i.end的情况，那么我们要考虑newInterval.start跟i.start的大小，两者取更小的作为newInterval的start即可。然后我们要找到这个newInterval跟哪些intervals.get(i)相overlap，那么其实只需要找到最后一个i.start小于等于newInterval.end的interval即可，那么更新newInterval.end为newInterval.end和i.end两者更大的即可。剩下后面的i.start都比newInterval.end要大，也不会有overlap，所以先把newInterval放进result里面，再把后面所有剩下的intervals放进result里面就可以了。

代码如下：
```java
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    List<Interval> result = new ArrayList<>();

    int i = 0;
    while (i < intervals.size() && intervals.get(i).end < newInterval.start) {
        result.add(intervals.get(i));
        i++;
    }
    if (i < intervals.size()) {
        newInterval.start = Math.min(newInterval.start, intervals.get(i).start);
    }
    while (i < intervals.size() && intervals.get(i).start <= newInterval.end) {
        newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
        i++;
    }
    result.add(newInterval);
    while (i < intervals.size()) {
        result.add(intervals.get(i));
        i++;
    }
    return result;
}
```


#套路总结
---
- 其实这个题就是对于一个复杂的问题拆分成多个简单问题的例子，每一个步骤单独看起来其实很简单，但是不容易从复杂问题想到，而且有一些corner case需要考虑，比如intervals的size为0的情况。

LeetCode 75 Sort Colors

#**LeetCode75**
---
https://leetcode.com/problems/sort-colors/description/

Yifeng Zeng

#题目描述
---
Sort Colors

#思路报告
---
拿到这个题最primitive的想法肯定是自己写一个quick sort/merge sort甚至直接调用Arrays.sort()。但这并没有利用到只有0，1，2三种color的特质，所以quick sort/merge sort明显就不再是考点了。既然我们已经知道了有固定3种颜色，那么我们可以用三个变量直接存一下每个颜色出现了多少次然后把每个颜色出现的次数对应回原array就可以了，这样的话可以做到时间O(n)，空间O(3)的情况，但是说白了这个O(3)就是O(k),k是color的个数，而当k等于n时这是不太好的，那么我们可不可以省略这个O(k)的空间而保持O(n)的时间呢？在线性array上能做的不要extra space的inplace操作其实就只有swap，那么我们就考虑swap。而要O(n)的时间，肯定是多个（k个）指针，一个指针指向array里0在的那一整块，一个指针指向1的那一整块，一个指针指向2的那一整块。对于一个整块里面不属于它的element进行swap操作。

代码如下

```java
    public void sortColors(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        int i = 0;
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            if (nums[l] == 0) {
                nums[l] = nums[i];
                nums[i] = 0;
                i++;
                l++;
            } else if (nums[l] == 1) {
                l++;
            } else if (nums[l] == 2) {
                nums[l] = nums[r];
                nums[r] = 2;
                r--;
            }
        }
    }
```

#套路总结
---
- array的inplace操作只能做swap，这个挺重要的，要有这个敏感度。