Leetcode 298 Binary Tree Longest Consecutive Sequence

Given a binary tree, find the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).

For example,

   1
    \
     3
    / \
   2   4
        \
         5

Longest consecutive sequence path is 3-4-5, so return 3.

   2
    \
     3
    / 
   2    
  / 
 1

Longest consecutive sequence path is 2-3,not3-2-1, so return 2.
Solution 1: Simple DFS and keep tracking the consecutive sequence will solve it.

 public class Solution {  
   public int longestConsecutive(TreeNode root) {  
     if (root==null) return 0;  
     int[] res=new int[1];  
     dfs(root,1,res);  
     return res[0];  
   }  
   private void dfs(TreeNode x, int len, int[] res) {  
     res[0]=Math.max(res[0],len);  
     if (x.left!=null) {  
       if (x.left.val==x.val+1) dfs(x.left,len+1,res);  
       else dfs(x.left,1,res);  
     }  
     if (x.right!=null) {  
       if (x.right.val==x.val+1) dfs(x.right,len+1,res);  
       else dfs(x.right,1,res);  
     }  
   }  
 }  

Leetcode 297 Serialize and Deserialize Binary Tree

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 tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Solution 1: use recursive DFS, pre-order traversal.

 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 x, StringBuilder sb) {  
     if (x==null) {  
       sb.append("null ");  
       return;  
     }  
     sb.append(String.valueOf(x.val));  
     sb.append(' ');  
     dfs(x.left,sb);  
     dfs(x.right,sb);  
   }  
   // Decodes your encoded data to tree.  
   public TreeNode deserialize(String data) {  
     String[] node=data.split(" ");  
     int[] d=new int[1];  
     return dfs(node,d);  
   }  
   private TreeNode dfs(String[] node, int[] d) {  
     if (node[d[0]].equals("null")) {  
       d[0]++;  
       return null;  
     }  
     TreeNode x=new TreeNode(Integer.valueOf(node[d[0]]));  
     d[0]++;  
     x.left=dfs(node,d);  
     x.right=dfs(node,d);  
     return x;  
   }  
 }  

Solution 2: Use iterative DFS, pre-order traversal.

 public class Codec {  
   // Encodes a tree to a single string.  
   public String serialize(TreeNode root) {  
     StringBuilder sb=new StringBuilder();  
     TreeNode x=root;  
     Deque<TreeNode> stack=new LinkedList<>();  
     while (x!=null || !stack.isEmpty()) {  
       if (x!=null) {  
         sb.append(String.valueOf(x.val));  
         sb.append(' ');  
         stack.push(x);  
         x=x.left;  
       }  
       else {  
         sb.append("null ");  
         x=stack.pop();  
         x=x.right;  
       }  
     }  
     return sb.toString();  
   }  
   // Decodes your encoded data to tree.  
   public TreeNode deserialize(String data) {  
     if (data.length()==0) return null;  
     String[] node=data.split(" ");  
     int n=node.length;  
     Deque<TreeNode> stack=new LinkedList<>();  
     TreeNode root=new TreeNode(Integer.valueOf(node[0]));  
     TreeNode x=root;  
     stack.push(x);  
     int i=1;  
     while (i<n) {  
       while (i<n && !node[i].equals("null")) {  
         x.left=new TreeNode(Integer.valueOf(node[i++]));  
         x=x.left;  
         stack.push(x);  
       }  
       while (i<n && node[i].equals("null")) {  
         x=stack.pop();  
         i++;  
       }  
       if (i<n) {  
         x.right=new TreeNode(Integer.valueOf(node[i++]));  
         x=x.right;  
         stack.push(x);  
       }  
     }  
     return root;  
   }  
 }  

Solution 3: Use BFS

 public class Codec {  
   // Encodes a tree to a single string.  
   public String serialize(TreeNode root) {  
     if (root==null) return "";  
     Queue<TreeNode> qu=new LinkedList<>();  
     StringBuilder sb=new StringBuilder();  
     qu.offer(root);  
     sb.append(String.valueOf(root.val));  
     sb.append(' ');  
     while (!qu.isEmpty()) {  
       TreeNode x=qu.poll();  
       if (x.left==null) sb.append("null ");  
       else {  
         qu.offer(x.left);  
         sb.append(String.valueOf(x.left.val));  
         sb.append(' ');  
       }  
       if (x.right==null) sb.append("null ");  
       else {  
         qu.offer(x.right);  
         sb.append(String.valueOf(x.right.val));  
         sb.append(' ');  
       }  
     }  
     return sb.toString();  
   }  
   // Decodes your encoded data to tree.  
   public TreeNode deserialize(String data) {  
     if (data.length()==0) return null;  
     String[] node=data.split(" ");  
     Queue<TreeNode> qu=new LinkedList<>();  
     TreeNode root=new TreeNode(Integer.valueOf(node[0]));  
     qu.offer(root);  
     int i=1;  
     while (!qu.isEmpty()) {  
       Queue<TreeNode> nextQu=new LinkedList<>();  
       while (!qu.isEmpty()) {  
         TreeNode x=qu.poll();  
         if (node[i].equals("null")) x.left=null;  
         else {  
           x.left=new TreeNode(Integer.valueOf(node[i]));  
           nextQu.offer(x.left);  
         }  
         i++;  
         if (node[i].equals("null")) x.right=null;  
         else {  
           x.right=new TreeNode(Integer.valueOf(node[i]));  
           nextQu.offer(x.right);  
         }  
         i++;  
       }  
       qu=nextQu;  
     }  
     return root;  
   }  
 }  

Leetcode 267 Palindrome Permutation II

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

For example:

Given s = "aabb", return ["abba", "baab"].

Given s = "abc", return [].

Solution 1:  Use back tracking, O((n/2)!) complexity.

 public class Solution {  
   public List<String> generatePalindromes(String s) {  
     int n=s.length();  
     int[] count=new int[256];  
     List<String> res=new ArrayList<>();  
     for (int i=0; i<n; i++) count[s.charAt(i)]++;  
     int odd=0;  
     for (int i=0; i<256; i++) {  
       if (count[i]%2!=0 && ++odd>1) return res;  
     }  
     char[] c=new char[n];  
     dfs(c,0,n-1,count,res);  
     return res;  
   }  
   private void dfs(char[] c, int lo, int hi, int[] count, List<String> res) {  
     if (lo>hi) res.add(new String(c));  
     else if (lo==hi) {  
       for (char i=0; i<256; i++) {  
         if (count[i]!=0) {  
           c[lo]=i;  
           res.add(new String(c));  
         }  
       }  
     }  
     else {  
       for (char i=0; i<256; i++) {  
         if (count[i]>=2) {  
           count[i]-=2;  
           c[lo]=i;  
           c[hi]=i;  
           dfs(c,lo+1,hi-1,count,res);  
           count[i]+=2;  
         }  
       }  
     }  
   }  
 }  

Leetcode 261 Graph Valid Tree

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Solution 1: Build the Graph then DFS

 public class Solution {  
   public boolean validTree(int n, int[][] edges) {  
     List<Integer>[] adj=new List[n];  
     for (int i=0; i<n; i++) adj[i]=new LinkedList<>();  
     for (int i=0; i<edges.length; i++) {  
       adj[edges[i][0]].add(edges[i][1]);  
       adj[edges[i][1]].add(edges[i][0]);  
     }  
     boolean[] marked=new boolean[n];  
     boolean[] hasCycle=new boolean[1];  
     dfs(adj,-1,0,hasCycle,marked);  
     for (int v=0; v<n; v++) {  
       if (!marked[v]) return false;  
     }  
     return !hasCycle[0];  
   }  
   private void dfs(List<Integer>[] adj, int s, int v, boolean[] hasCycle, boolean[] marked) {  
     marked[v]=true;  
     for (int w: adj[v]) {  
       if (hasCycle[0]) return;  
       else if (w!=s) {  
         if (!marked[w]) dfs(adj,v,w,hasCycle,marked);  
         else hasCycle[0]=true;  
       }  
     }  
   }  
 }  

Solution 2: Uni-Find

 public class Solution {  
   public boolean validTree(int n, int[][] edges) {  
     int[] nums=new int[n];  
     Arrays.fill(nums,-1);  
     for (int[] edge: edges) { //check loop  
       int x=edge[0], y=edge[1];  
       int c1=0, c2=0;  
       while (nums[x]!=-1) {  
         x=nums[x];  
         c1++;  
       }  
       while (nums[y]!=-1) {  
         y=nums[y];  
         c2++;  
       }  
       if (x==y) return false;  
       if (c1>c2) nums[y]=x;//connected small part to big part  
       else nums[x]=y;  
     }  
     int count=0; //check all connected, nums of -1 is nums of cc  
     for (int i=0; i<n; i++) {  
       if (nums[i]==-1 && ++count>1) return false;  
     }  
     return true;  
   }  
 }  

Leetcode 254 Factor Combinations

Numbers can be regarded as product of its factors. For example,

8 = 2 x 2 x 2;
  = 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

Note: 

1. Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is [2, 6], not [6, 2].
2. You may assume that n is always positive.
3. Factors should be greater than 1 and less than n.

Examples: 
input: 1
output: 

[]

input: 37
output: 

[]

input: 12
output:

[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

input: 32
output:

[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

Solution 1: DFS

 public class Solution {  
   public List<List<Integer>> getFactors(int n) {  
     List<Integer> one=new ArrayList<>();  
     List<List<Integer>> res=new ArrayList<>();  
     for (int i=2; i*i<=n; i++) dfs(i,n,one,res);  
     return res;  
   }  
   private void dfs(int d, int n, List<Integer> one, List<List<Integer>> res) {  
     if (n%d!=0) return;  
     one.add(d);  
     n/=d;  
     one.add(n);  
     res.add(new ArrayList<Integer>(one));  
     one.remove(one.size()-1);  
     for (int i=d; i*i<=n; i++) dfs(i,n,one,res);  
     one.remove(one.size()-1);  
   }  
 }  

Leetcode 247 Strobogrammatic Number II

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Find all strobogrammatic numbers that are of length = n.

For example,
Given n = 2, return ["11","69","88","96"].

Solution 1: back tracking to build all the numbers.

 public class Solution {  
   public List<String> findStrobogrammatic(int n) {  
     List<String> res=new ArrayList<>();  
     if (n<=0) return res;  
     char[] c=new char[n];  
     dfs(c,0,n-1,res);  
     return res;  
   }  
   private void dfs(char[] c, int i, int j, List<String> res) {  
     if (i>j) res.add(new String(c));  
     else {  
       if (i>0 || (i==0 && j==0)) {  
         c[i]='0';c[j]='0';  
         dfs(c,i+1,j-1,res);  
       }  
       if (i!=j) {  
         c[i]='6';c[j]='9';  
         dfs(c,i+1,j-1,res);  
         c[i]='9';c[j]='6';  
         dfs(c,i+1,j-1,res);  
       }  
       c[i]='1';c[j]='1';  
       dfs(c,i+1,j-1,res);  
       c[i]='8';c[j]='8';  
       dfs(c,i+1,j-1,res);  
     }  
   }  
 }  

Leetcode 230 Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: 
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Solution 1: use in-order traversal and counter the kth number.

 public class Solution {  
   public int kthSmallest(TreeNode root, int k) {  
     Deque<TreeNode> stack=new LinkedList<>();  
     TreeNode x=root;  
     while (x!=null || !stack.isEmpty()) {  
       if (x!=null) {  
         stack.push(x);  
         x=x.left;  
       }  
       else {  
         x=stack.pop();  
         if (--k==0) return x.val;  
         x=x.right;  
       }  
     }  
     return 0;  
   }  
 }  

Leetcode 216 Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Ensure that numbers within the set are sorted in ascending order.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

Solution 1: Use back tracking method. Terminate condition is (1) reach depth of k, generate possible result. (2) num>9 not valid, (3) num>n, not valid as in ascending  order.

 public class Solution {  
   public List<List<Integer>> combinationSum3(int k, int n) {  
     List<List<Integer>> res=new ArrayList<>();  
     if (k>9 || k<0) return res;  
     if (n<1 || n>45) return res;  
     List<Integer> one=new ArrayList<>();  
     dfs(0,1,k,n,one,res);  
     return res;  
   }  
   private void dfs(int d, int num, int k, int n, List<Integer> one, List<List<Integer>> res) {  
     if (d==k) {  
       if (n==0) res.add(new ArrayList<Integer>(one));  
     }  
     else if (num<=9 && num<=n) {  
       dfs(d,num+1,k,n,one,res);  
       one.add(num);  
       dfs(d+1,num+1,k,n-num,one,res);  
       one.remove(one.size()-1);  
     }  
   }  
 }  

Leetcode 212 Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example,
Given words = ["oath","pea","eat","rain"] and board =

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return ["eat","oath"].

Note:
You may assume that all inputs are consist of lowercase letters a-z.

Solution 1: the combination of graph and trie. First use dictionary to build the trie. Then DFS the char array to come up the result list.

 public class Solution {  
   class TrieNode {  
     private boolean val=false;  
     private TrieNode[] next=new TrieNode[26];  
   }  
   private TrieNode root=new TrieNode();  
   private void add(String word) {  
     TrieNode x=root;  
     int i=0;  
     while (i<word.length()) {  
       int index=word.charAt(i++)-'a';  
       if (x.next[index]==null) x.next[index]=new TrieNode();  
       x=x.next[index];  
     }  
     x.val=true;  
   }  
   private TrieNode search(String word) {  
     TrieNode x=root;  
     int i=0;  
     while (i<word.length()) {  
       int index=word.charAt(i++)-'a';  
       if (x.next[index]==null) return null;  
       x=x.next[index];  
     }  
     return x;  
   }  
   private boolean findOne(String word) {  
     TrieNode x=search(word);  
     if (x==null) return false;  
     return x.val;  
   }  
   private boolean findPrefix(String word) {  
     TrieNode x=search(word);  
     if (x==null) return false;  
     return true;  
   }  
   public List<String> findWords(char[][] board, String[] words) {  
     Set<String> res=new HashSet<>();  
     for (String s:words) add(s);  
     int m=board.length;  
     if (m==0) return new ArrayList<String>(res);  
     int n=board[0].length;  
     String s="";  
     for (int i=0; i<m; i++) {  
       for (int j=0; j<n; j++) {  
         dfs(board,i,j,m,n,s,res);  
       }  
     }  
     return new ArrayList<String>(res);  
   }  
   private void dfs(char[][] board, int i, int j, int m, int n, String s, Set<String> res) {  
     if (i<0 || i>=m) return;  
     if (j<0 || j>=n) return;  
     if (board[i][j]=='.') return;  
     char c=board[i][j];  
     String word=s+c;  
     if (!findPrefix(word)) return;  
     if (findOne(word)) res.add(word);  
     board[i][j]='.';  
     dfs(board,i+1,j,m,n,word,res);  
     dfs(board,i-1,j,m,n,word,res);  
     dfs(board,i,j+1,m,n,word,res);  
     dfs(board,i,j-1,m,n,word,res);  
     board[i][j]=c;  
   }  
 }  

Leetcode 210 Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Solution 1: build the graph, then DFS to judge if there is loop. If not topo sort.

 public class Solution {  
   public int[] findOrder(int numCourses, int[][] prerequisites) {  
     int V=numCourses;  
     List<Integer>[] adj=new List[V];  
     for (int v=0; v<V; v++) adj[v]=new LinkedList<>();  
     for (int i=0; i<prerequisites.length; i++) adj[prerequisites[i][1]].add(prerequisites[i][0]);  
     boolean[] marked=new boolean[V];  
     boolean[] onStack=new boolean[V];  
     boolean[] hasCycle=new boolean[1];  
     Deque<Integer> stack=new LinkedList<>();  
     for (int v=0; v<V; v++)  
       if (!marked[v]) dfs(v,adj,V,marked,onStack,hasCycle,stack);  
     if (hasCycle[0]) return new int[0];  
     int[] res=new int[V];  
     for (int i=0; i<V; i++) res[i]=stack.pop();  
     return res;  
   }  
   private void dfs(int v, List<Integer>[] adj, int V, boolean[] marked, boolean[] onStack, boolean[] hasCycle, Deque<Integer> stack) {  
     marked[v]=true;  
     onStack[v]=true;  
     for (int w:adj[v]) {  
       if (hasCycle[0]) return;  
       else if (!marked[w]) dfs(w,adj,V,marked,onStack,hasCycle,stack);  
       else if(onStack[w]) hasCycle[0]=true;  
     }  
     stack.push(v);  
     onStack[v]=false;  
   }  
 }  

Leetcode 207 Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Solution 1: Directed graph loop question. Build the graph and then DFS.

 public class Solution {  
   public boolean canFinish(int numCourses, int[][] prerequisites) {  
     int V=numCourses;  
     List<Integer>[] adj=new List[V];  
     for (int v=0; v<V; v++) adj[v]=new LinkedList<>();  
     for (int i=0; i<prerequisites.length; i++) adj[prerequisites[i][1]].add(prerequisites[i][0]);  
     boolean[] marked=new boolean[V];  
     boolean[] onStack=new boolean[V];  
     boolean[] hasCycle=new boolean[1];  
     for (int v=0; v<V; v++)  
       if(!marked[v]) dfs(v,adj,V,marked,onStack,hasCycle);  
     return !hasCycle[0];  
   }  
   private void dfs(int v, List<Integer>[] adj, int V, boolean[] marked, boolean[] onStack, boolean[] hasCycle) {  
     marked[v]=true;  
     onStack[v]=true;  
     for (int w: adj[v]) {  
       if (hasCycle[0]) return;  
       else if (!marked[w]) dfs(w,adj,V,marked,onStack,hasCycle);  
       else if (onStack[w]) hasCycle[0]=true;  
     }  
     onStack[v]=false;  
   }  
 }  

Leetcode 200 Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

Solution 1: max CC question in graph, use DFS.

 public class Solution {  
   public int numIslands(char[][] grid) {  
     int m=grid.length;  
     if (m==0) return 0;  
     int n=grid[0].length;  
     int count=0;  
     for (int i=0; i<m; i++) {  
       for (int j=0; j<n; j++) {  
         if (grid[i][j]=='1') {  
           count++;  
           dfs(grid,i,j,m,n);  
         }  
       }  
     }  
     return count;  
   }  
   private void dfs(char[][] grid, int i, int j, int m, int n) {  
     if (i<0 || i>=m) return;  
     if (j<0 || j>=n) return;  
     if (grid[i][j]!='1') return;  
     grid[i][j]='x';  
     dfs(grid,i+1,j,m,n);  
     dfs(grid,i-1,j,m,n);  
     dfs(grid,i,j+1,m,n);  
     dfs(grid,i,j-1,m,n);  
   }  
 }  

Leetcode 173 Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

Solution 1: Use iterative in-order traversal.

 public class BSTIterator {  
   private TreeNode x;  
   private Deque<TreeNode> stack;  
   public BSTIterator(TreeNode root) {  
     stack=new LinkedList<>();  
     x=root;  
     while (x!=null) {  
       stack.push(x);  
       x=x.left;  
     }  
   }  
   /** @return whether we have a next smallest number */  
   public boolean hasNext() {  
     return !stack.isEmpty();  
   }  
   /** @return the next smallest number */  
   public int next() {  
     x=stack.pop();  
     int res=x.val;  
     x=x.right;  
     while (x!=null) {  
       stack.push(x);  
       x=x.left;  
     }  
     return res;  
   }  
 }}  

Leetcode 145 Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Solution 1: Recursive DFS, too easy, similar to pre-order.

Solution 2: Iterative DFS.

 public class Solution {  
   public List<Integer> postorderTraversal(TreeNode root) {  
     Deque<TreeNode> stack=new LinkedList<>();  
     List<Integer> res=new ArrayList<>();  
     TreeNode x=root;  
     TreeNode last=null;  
     while (x!=null || !stack.isEmpty()) {  
       if (x!=null) {  
         stack.push(x);  
         x=x.left;  
       }  
       else {  
         TreeNode peek=stack.peek();  
         if (peek.right==null || peek.right==last) {  
           last=stack.pop();  
           res.add(last.val);  
         }  
         else {  
           x=peek.right;  
         }  
       }  
     }  
     return res;  
   }  
 }  

Leetcode 144 Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

Solution 1: recursive DFS

 public class Solution {  
   public List<Integer> preorderTraversal(TreeNode root) {  
     List<Integer> res=new ArrayList<>();  
     dfs(root,res);  
     return res;  
   }  
   private void dfs(TreeNode x, List<Integer> res) {  
     if (x==null) return;  
     res.add(x.val);  
     dfs(x.left, res);  
     dfs(x.right, res);  
   }  
 }  

Solution 2: iterative DFS

 public class Solution {  
   public List<Integer> preorderTraversal(TreeNode root) {  
     Deque<TreeNode> stack=new LinkedList<>();  
     List<Integer> res=new ArrayList<>();  
     TreeNode x=root;  
     while (x!=null || !stack.isEmpty()) {  
       if (x!=null) {  
         res.add(x.val);  
         stack.push(x);  
         x=x.left;  
       }  
       else {  
         x=stack.pop();  
         x=x.right;  
       }  
     }  
     return res;  
   }  
 }  

Leetcode 140 Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

Solution 1: first use DP to build up if [i...j] is in dict or not, then use DFS to collect all the possible breaks. The thing is to make judgement first, only if there is solution then dfs.

 public class Solution {  
   public List<String> wordBreak(String s, Set<String> wordDict) {  
     char[] c=s.toCharArray();  
     int n=c.length;  
     boolean[][] dp=new boolean[n][n];  
     boolean[] exist=new boolean[n+1];  
     List<String> res=new ArrayList<>();  
     List<String> one=new ArrayList<>();  
     if (n==0) return res;  
     exist[0]=true;  
     for (int j=0; j<n; j++){  
       exist[j+1]=false;  
       for (int i=0; i<=j; i++) {  
         dp[i][j]=wordDict.contains(new String(c,i,j-i+1))?true:false;  
         if (dp[i][j] && exist[i]) exist[j+1]=true;  
       }  
     }  
     if (exist[n]) dfs(c,dp,0,one,res);  
     return res;  
   }  
   private void dfs(char[] c, boolean[][] dp, int d, List<String> one, List<String> res) {  
     if (d==c.length) {  
       StringBuilder sb=new StringBuilder();  
       for (String s:one) {  
         sb.append(s);  
         sb.append(' ');  
       }  
       res.add(sb.substring(0,sb.length()-1));  
     }  
     else {  
       for (int i=d; i<c.length; i++) {  
         if (dp[d][i]) {  
           one.add(new String(c,d,i-d+1));  
           dfs(c,dp,i+1,one,res);  
           one.remove(one.size()-1);  
         }  
       }  
     }  
   }  
 }  

Leetcode 138 Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Solution 1: use graph copy method, it can deal with the random list even it has loop. Below is an example of BFS.

 public class Solution {  
   public RandomListNode copyRandomList(RandomListNode head) {  
     if (head==null) return null;  
     Map<RandomListNode,RandomListNode> map=new HashMap<>();  
     Queue<RandomListNode> qu=new LinkedList<>();  
     RandomListNode x=new RandomListNode(head.label);  
     map.put(head,x);  
     qu.offer(head);  
     while (!qu.isEmpty()) {  
       RandomListNode v=qu.poll();  
       if (v.next!=null && !map.containsKey(v.next)) {  
         RandomListNode w1=new RandomListNode(v.next.label);  
         map.put(v.next,w1);  
         qu.offer(v.next);  
       }  
       if (v.random!=null && !map.containsKey(v.random)) {  
         RandomListNode w2=new RandomListNode(v.random.label);  
         map.put(v.random,w2);  
         qu.offer(v.random);  
       }  
       if (v.next!=null) map.get(v).next=map.get(v.next);  
       if (v.random!=null) map.get(v).random=map.get(v.random);  
     }  
     return map.get(head);  
   }  
 }  

Solution 2: if we know that there is no loop. Code can be much cleaner.

 public class Solution {  
   public RandomListNode copyRandomList(RandomListNode head) {  
     if (head==null) return null;  
     Map<RandomListNode,RandomListNode> map=new HashMap<>();  
     RandomListNode x=head;  
     while (x!=null) {  
       RandomListNode w=new RandomListNode(x.label);  
       map.put(x,w);  
       x=x.next;  
     }  
     x=head;  
     while (x!=null) {  
       map.get(x).next=map.get(x.next);  
       map.get(x).random=map.get(x.random);  
       x=x.next;  
     }  
     return map.get(head);  
   }  
 }  

Leetcode 133 Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Solution 1: Recursive dfs. O(E)

 public class Solution {  
   public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {  
     if (node==null) return null;  
     Map<UndirectedGraphNode,UndirectedGraphNode> map=new HashMap<>();  
     dfs(map,node);  
     return map.get(node);  
   }  
   private void dfs(Map<UndirectedGraphNode,UndirectedGraphNode> map, UndirectedGraphNode v) {  
     UndirectedGraphNode x=new UndirectedGraphNode(v.label);  
     map.put(v,x);  
     for (UndirectedGraphNode w: v.neighbors) {  
       if (!map.containsKey(w)) dfs(map,w);  
       x.neighbors.add(map.get(w));  
     }  
   }  
 }  

Solution 2: BFS

 public class Solution {  
   public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {  
     if (node==null) return null;  
     Queue<UndirectedGraphNode> qu=new LinkedList<>();  
     Map<UndirectedGraphNode, UndirectedGraphNode> map=new HashMap<>();  
     UndirectedGraphNode x=new UndirectedGraphNode(node.label);  
     map.put(node,x);  
     qu.offer(node);  
     while (!qu.isEmpty()) {  
       UndirectedGraphNode v=qu.poll();  
       for (UndirectedGraphNode w: v.neighbors) {  
         if (!map.containsKey(w)) {  
           map.put(w, new UndirectedGraphNode(w.label));  
           qu.offer(w);  
         }  
         map.get(v).neighbors.add(map.get(w));  
       }  
     }  
     return map.get(node);  
   }  
 }  

Leetcode 131 Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

Solution 1: DP + DFS: use DP to store if s[i..j] is palindrome or not. This  will guarantee to be O(N^2) complexity.

 public class Solution {  
   public List<List<String>> partition(String s) {  
     int n=s.length();  
     char c[]=s.toCharArray();  
     boolean[][] dp=new boolean[n][n];//store if s[i..j] is palin or not  
     for (int j=0; j<n; j++) {  
       for (int i=j; i>=0; i--) {  
         if (j==i) dp[i][j]=true;  
         else dp[i][j]=c[i]==c[j] && (i+1>=j-1 || dp[i+1][j-1]);  
       }  
     }  
     List<String> one=new ArrayList<>();  
     List<List<String>> res=new ArrayList<>();  
     dfs(c,0,dp,one,res);  
     return res;  
   }  
   private void dfs(char[] c, int d, boolean[][] dp, List<String> one, List<List<String>> res) {  
     if (d==c.length) res.add(new ArrayList<String>(one));  
     else {  
       for (int j=d; j<c.length; j++) {  
         if (dp[d][j]) {  
           one.add(new String(c,d,j-d+1));  
           dfs(c,j+1,dp,one,res);  
           one.remove(one.size()-1);  
         }  
       }  
     }  
   }  
 }  

Leetcode 129 Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Solution 1: DFS, when reach to leaf, add the result.

 public class Solution {  
   public int sumNumbers(TreeNode root) {  
     int[] res=new int[1];  
     dfs(root,0,res);  
     return res[0];  
   }  
   private void dfs(TreeNode x, int num, int[] res) {  
     if (x==null) return;  
     num=num*10+x.val;  
     if (x.left==null && x.right==null) res[0]+=num;  
     dfs(x.left,num,res);  
     dfs(x.right,num,res);  
   }  
 }