Leetcode: Expression Add Operators

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Examples: 

"123", 6 -> ["1+2+3", "1*2*3"] 
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []

Understand the problem:
A classic DFS problem. 


Code (Java):

public class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> result = new ArrayList<>();
        
        if (num == null || num.length() == 0) {
            return result;
        }
        
        addOperatorHelper(num, 0, target, 0, 0, "", result);
        
        return result;
    }
    
    private void addOperatorHelper(String num, int start, int target, long curSum, 
                   long preNum, String curResult, List<String> result) {
        if (start == num.length() && curSum == target) {
            result.add(curResult);
            return;
        }
        
        if (start == num.length()) {
            return;
        }
        
        for (int i = start; i < num.length(); i++) {
            String curStr = num.substring(start, i + 1);
            if (curStr.length() > 1 && curStr.charAt(0) == '0') {
                break;
            }
            
            long curNum = Long.parseLong(curStr);
            
            if (curResult.isEmpty()) {
                addOperatorHelper(num, i + 1, target, curNum, curNum, curStr, result);
            } else {
                // Multiply
                addOperatorHelper(num, i + 1, target, curSum - preNum + preNum * curNum, 
                                  preNum * curNum, curResult + "*" + curNum, result);
                
                // Add
                addOperatorHelper(num, i + 1, target, curSum + curNum, curNum, 
                                  curResult + "+" + curNum, result);
                
                // Subtract
                addOperatorHelper(num, i + 1, target, curSum - curNum, -curNum, 
                                  curResult + "-" + curNum, result);
            }
        }
    }
}

Leetcode: 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

Understand the problem:

This problem is an alternative view of connected components in a undirected graph. It could be easily solved by using either DFS or BFS. 

DFS Solution (Java):

public class Solution {
    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;
        
        boolean[][] visited = new boolean[rows][cols];
        int result = 0;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    result++;
                    numIslandsHelper(grid, visited, i, j, rows, cols);
                }
            }
        }
        
        return result;
    }
    
    private void numIslandsHelper(char[][] grid, boolean[][] visited, int i, int j, int numRows, int numCols) {
        if (i < 0 || i >= numRows) {
            return;
        }
        
        if (j < 0 || j >= numCols) {
            return;
        }
        
        if (visited[i][j]) {
            return;
        }
        
        // If water
        if (grid[i][j] == '0') {
            return;
        }
        
        // Mark the visted[i][j] = true
        visited[i][j] = true;
        
        // Go up, down, left and right
        numIslandsHelper(grid, visited, i - 1, j, numRows, numCols);
        numIslandsHelper(grid, visited, i + 1, j, numRows, numCols);
        numIslandsHelper(grid, visited, i, j - 1, numRows, numCols);
        numIslandsHelper(grid, visited, i, j + 1, numRows, numCols);
    }
}

A BFS Solution:

public class Solution {
    private Queue<Integer> queue = new LinkedList();
    
    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;
        boolean[][] visited = new boolean[rows][cols];
        
        int result = 0;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    result++;
                    numIslandsHelper(grid, visited, i, j, rows, cols);
                }
            }
        }
        return result;
    }
    
    private void numIslandsHelper(char[][] grid, boolean[][] visited, int i, int j, int numRows, int numCols) {
        fill(grid, visited, i, j, numRows, numCols);
        
        while (!queue.isEmpty()) {      
            int cord = queue.poll();
            int x = cord / numCols;
            int y = cord % numCols;
    
            fill(grid, visited, x - 1, y, numRows, numCols);
            fill(grid, visited, x + 1, y, numRows, numCols);
            fill(grid, visited, x, y - 1, numRows, numCols);
            fill(grid, visited, x, y + 1, numRows, numCols);
        }
    }
    
    private void fill(char[][] grid, boolean[][] visited, int i, int j, int numRows, int numCols) {
        if (i < 0 || i >= numRows || j < 0 || j >= numCols) {
            return;
        }
        
        if (visited[i][j] || grid[i][j] == '0') {
            return;
        }
        
        visited[i][j] = true;
        
        queue.offer(i * numCols + j);
    }
}

Update on 1/25/16:
Union-find Solution:

public class Solution {
    private int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int m = grid.length;
        int n = grid[0].length;
        
        int[] parents = new int[m * n];
        int count = 0;
        
        // Step 1: initialize each node, for each's parent is itself
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int id = i * n + j;
                parents[id] = id;
            }
        }
        
        // step 2: iterate each node, and connect the neighbors
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '0') {
                    continue;
                }
                
                for (int[] row : dir) {
                    int x = i + row[0];
                    int y = j + row[1];
                    if (isValid(grid, x, y)) {
                        int p = i * n + j;
                        int q = x * n + y;
                        connect(parents, p, q);
                    }
                }
            }
        }
        
        // step 3: count the number of cc
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int id = i * n + j;
                if (grid[i][j] == '1' && parents[id] == id) {
                    count++;
                }
            }
        }
        
        return count;
    }
    
    private boolean isValid(char[][] grid, int x, int y) {
        int m = grid.length;
        int n = grid[0].length;
        
        return x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1';
    }
    
    private void connect(int[] parents, int p, int q) {
        int pRoot = find(parents, p);
        int qRoot = find(parents, q);
        
        if (pRoot == qRoot) {
            return;
        }
        
        parents[pRoot] = qRoot;
    }
    
    private int find(int[] parents, int id) {
        while (parents[id] != id) {
            id = parents[id];
        }
        
        return id;
    }
}

Updata on 4/21/19:

public class Solution {
    /**
     * @param grid: a boolean 2D matrix
     * @return: an integer
     */
    public int numIslands(boolean[][] grid) {
        // write your code here
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int nRows = grid.length;
        int nCols = grid[0].length;
        
        int[] parents = new int[nRows * nCols];
        for (int i = 0; i < parents.length; i++) {
            parents[i] = i;
        }
        
        for (int i = 0; i < nRows; i++) {
            for (int j = 0; j < nCols; j++) {
                if (grid[i][j]) {
                    union(grid, i, j, parents);
                }
            }
        }
        
        int numIslands = 0;
        
        for (int i = 0; i < parents.length; i++) {
            int nx = i / nCols;
            int ny = i % nCols;
            
            if (grid[nx][ny] && parents[i] == i) {
                numIslands++;
            }
        }
        
        return numIslands;
    }
    
    private void union(boolean[][] grid, int x, int y, int[] parents) {
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        int nRows = grid.length;
        int nCols = grid[0].length;
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dirs[i][0];
            int ny = y + dirs[i][1];
            
            if (nx >= 0 && nx < nRows && ny >= 0 && ny < nCols && grid[nx][ny]) {
                int myParrent = find(parents, x * nCols + y);
                int neighborParrent = find(parents, nx * nCols + ny);
                
                if (myParrent != neighborParrent) {
                    parents[myParrent] = neighborParrent;
                }
            }
        }
    }
    
    private int find(int[] parents, int x) {
        int root = x;
        while (parents[root] != root) {
            root = parents[root];
        }
        
        // path compression
        //
        while (x != root) {
            int temp = parents[x];
            parents[x] = root;
            x = temp;
        }
        
        return root;
    }
}

Leetcode: Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Understand the problem:
The marginal 'O' cannot be surrounded. In addition, the adjacent 'O' to the marginal 'O' cannot be surrounded as well. So We can mark those 'O' as the other characters, like 'D'. Then mark the other 'O's as 'X', and mark 'D' as 'O'. 

Recursive Solution:
We start from the marginal points, and if it is 'O', we check its neighbored points. 

Code (Java):

public class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        
        int m = board.length;
        int n = board[0].length;
        
        // check the first and last rows
        for (int i = 0; i < n; i++) {
            solveHelper(0, i, m, n, board);
            solveHelper(m - 1, i, m, n, board);
        }
        
        for (int i = 1; i < m - 1; i++) {
            solveHelper(i, 0, m, n, board);
            solveHelper(i, n - 1, m, n, board);
        }
        
        // fill
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == 'D') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    
    private void solveHelper(int row, int col, int m, int n, char[][] board) {
        if (row < 0 || row >= m || col < 0 || col >= n || board[row][col] != 'O') {
            return;
        }
        
        board[row][col] = 'D';
        
        solveHelper(row - 1, col, m, n, board);
        solveHelper(row + 1, col, m, n, board);
        solveHelper(row, col - 1, m, n, board);
        solveHelper(row, col + 1, m, n, board);
        
    }
}

BFS Solution:

public class Solution {
    Queue<Integer> queue = new LinkedList<Integer>();
    public void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        
        int m = board.length;
        int n = board[0].length;
        
        for (int i = 0; i < n; i++) {
            solveHelper(0, i, m, n, board);
            solveHelper(m - 1, i, m, n, board);
        }
        
        for (int i = 1; i < m - 1; i++) {
            solveHelper(i, 0, m, n, board);
            solveHelper(i, n - 1, m, n, board);
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == 'D') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    
    private void solveHelper(int row, int col, int m, int n, char[][] board) {
        fill(row, col, m, n, board);
        
        while (!queue.isEmpty()) {
            int cord = queue.poll();
            int x = cord / n;
            int y = cord % n;
            
            fill(x - 1, y, m, n, board);
            fill(x + 1, y, m, n, board);
            fill(x, y - 1, m, n, board);
            fill(x, y + 1, m, n, board);
        }
    }
    
    private void fill(int row, int col, int m, int n, char[][] board) {
        if (row < 0 || row >= m || col < 0 || col >= n || board[row][col] != 'O') {
            return;
        } 
        
        board[row][col] = 'D';
        
        queue.offer(row * n + col);
    }
}

Leetcode: Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle...

...and its solution numbers marked in red.

Understand the problem:
The problem asks for finding an unique solution for a sudoku solver. We assume that there is an unique solution existed in the sudoku solver. So the basic idea could be using DFS, very similar with permutation and combination problem. We search all valid numbers for a slot, apply DFS, and go to the next. 

Solution:

public class Solution {
    public void solveSudoku(char[][] board) {
        if (board == null || board.length != 9 || board[0].length != 9) {
            return;
        }
        
        solveHelper(board);
    }
    
    private boolean solveHelper(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char k = '1'; k <= '9'; k++) {
                        if (isValid(i, j, k, board)) {
                            board[i][j] = k;
                            if (solveHelper(board) == true) {
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    private boolean isValid(int row, int col, char target, char[][] board) {
        // check the row and column
        for (int i = 0; i < 9; i++) {
            if ((board[row][i] == target) || (board[i][col] == target)) {
                return false;
            }
        }
        
        // check the block
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                int x = row / 3 * 3 + i; // nth block * block_size  + offset
                int y = col / 3 * 3 + j;
                if (board[x][y] == target) {
                    return false;
                }
            }
        }
        return true;
    }
}

Discussion:
Now let's analyze the complexity. Suppose the sudoku size is n (although in reality it is 9). For each slot which could be filled, we could have at most O(n) different combinations. For each number, it takes O(n) time to determine if it is a valid number. So we have total number of n^2 numbers in the board, the overall time complexity is O(n^4). For the real case where n equals to 9, the complexity is acceptable. 


Summary:
The problem follows the same idea as permutation and combination problem, where DFS is widely used in searching problems. Draw a recursion tree will help you understand the problem.

Leetcode: Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Understand the problem:
The problem asks for finding the longest palindromic substring in string S. The problem assumes that there is only one unique longest palindromic substring, and we are asked to return that substring. 

Naive Solution:
One straight-forward solution is to check each substring and determine if it is palindromic. So looping over each substring take O(n^2) time and checking each substring takes O(n) time. The total time complexity is O(n^3). 

DP Solution:
This question is quite similar to the Palindrome partitioning II, where return the minimum number of cuts such that all substrings are palindrome. The minimum cuts are equal to the longest palindrome. So we can still use the same idea to solve this problem.

In the palindrome partitioning II problem, we used an array dp[i] to indicate the minimum number of cuts from i to the end. However, in this problem, the longest palindromic substring does not always start from the first character of the input string; it can start from anywhere else. So we don't need to maintain an array dp[i] and check the results in dp[0]. Instead, whenever we found string[i, j] is a palindrome, we check its length. If it is the maximum, we keep it. In this way, we only keep the longest palindromic substring. The way to determine if a string from [i, j] is palindromic is the same as before.  

Code (Java):

public class Solution {
    public String longestPalindrome(String s) {
        String longestStr = null;
        int maxLen = 0;
        
        if (s == null || s.isEmpty()) return s;
        
        int len = s.length();
        boolean[][] palin = new boolean[len][len];
        
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if ((s.charAt(i) == s.charAt(j) && (j - i) < 2) || (s.charAt(i) == s.charAt(j) && palin[i + 1][j - 1])) {
                    palin[i][j] = true;
                    int temp = j - i + 1;
                    if (temp > maxLen) {
                        maxLen = temp;
                        longestStr = s.substring(i, j + 1);
                    }
                }
            }
        }
        return longestStr;
    }
}

Discussion:
So we see that both time and space complexity is O(n^2) for this solution. 


O(1) Space solution:
We can even develop a O(1) space solution. For a string is palindrome, it must be mirrored across a central point. Here we must consider both the even and odd length of the string. For a string with odd length, e.g. aa, it is palindromic for s[lo] == s[hi] where lo = 0, and hi = 1. For odd length, e.g. aba, lo = 0, and hi = 2. So we can iterate the string and check its left and right points to see if it is mirrored. 

Code (Java):

public class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len <= 1) return s;
        
        int start = 0;
        String longestSub = "";
        int maxLen = 0;
        
        for (int i = 1; i < len; i++) {
            //check the longest palindromic substring with even length;
            int lo = i - 1;
            int hi = i;
            
            while (lo >= 0 && hi < len && s.charAt(lo) == s.charAt(hi)) {
                lo--;
                hi++;
            }
            
            if ((hi - lo - 1) > maxLen) {
                maxLen = hi - lo - 1;
                start = lo + 1;
            }
            
            // check the longest palindromic substring with odd length
            lo = i - 1;
            hi = i + 1;
            
            while (lo >= 0 && hi < len && s.charAt(lo) == s.charAt(hi)) {
                lo--;
                hi++;
            }
            
            if ((hi - lo - 1) > maxLen) {
                maxLen = hi - lo - 1;
                start = lo + 1;
            }
        }
        return s.substring(start, start + maxLen);
    }
}

Discussion:
We can see that the solution above has time complexity of (n^2) since each point we need to check its left and right sides. The space complexity is (1).
Summary:
In this post, we learned how to find the longest palindromic substring. It is a classic problem. The DP solution is classic as well. Make sure you can apply it to other DP problems. Actually, there exists another method with time complexity of O(n). It is kind of complicated so we don't cover it here. 

Update on 11/26/14:

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }    
        
        int start = 0;
        int len = 1;
        
        for (int i = 0; i < s.length(); i++) {
            int curLen = 0;
            // For even length
            int lo = i;
            int hi = i + 1;
            while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) {
                curLen += 2;
                lo--;
                hi++;
            }
            if (curLen > len) {
                len = curLen;
                start = lo + 1;
            } 
            // For odd length
            lo = i - 1;
            hi = i + 1;
            curLen = 1;
            while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) {
                curLen += 2;
                lo--;
                hi++;
            }
            
            if (curLen > len) {
                len = curLen;
                start = lo + 1;
            }
        }
        return s.substring(start, start + len);
    }
}

Update on 4/7/2019

public class Solution {
    /**
     * @param s: input string
     * @return: the longest palindromic substring
     */
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        
        int maxLen = 0;
        int startIdx = 0;
        
        for (int i = 0; i < s.length(); i++) {
            int lenEven = findLongestPalin(s, i, i + 1);
            int lenOdd = findLongestPalin(s, i - 1, i + 1) + 1;
            
            if (lenEven > lenOdd && lenEven > maxLen) {
                maxLen = lenEven;
                startIdx = i - lenEven / 2 + 1;
            } else if (lenOdd > lenEven && lenOdd > maxLen) {
                maxLen = lenOdd;
                startIdx = i - lenOdd / 2;
            }
        }
        
        return s.substring(startIdx, maxLen + startIdx);
    }
    
    private int findLongestPalin(String s, int start, int end) {
        int ans = 0;
        
        while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
            start--;
            end++;
            ans += 2;
        }
        
        return ans;
    }
}

Leetcode: Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Understand the problem:

The problem asks for traverse the binary tree in order. The mainly difference between the BFS is it asks for returning the result bottom-up.

Naive Solution:

One native solution is to still use the pre-order traversal of the tree, and save the level, like how we solved the BFS problem recursively. The major difference is instead of appending the list of each level, we add them at front of the result list, and move others forward. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        
        levelOrderBottom(root, result, 1);
        
        return result;
    }
    
    private void levelOrderBottom(TreeNode root, ArrayList<ArrayList>Integer>> result, int level) {
        if (root == null) return;
        
        if (result.size() < level) {
            ArrayList<Integer> levelList = new ArrayList<Integer>();
            levelList.add(root.val);
            result.add(0, levelList);
        } else {
            result.get(result.size() - level).add(root.val);
        }
        
        levelOrderBottom(root.left, result, level + 1);
        levelOrderBottom(root.right, result, level + 1);
    }
}

Discussion:
Now let's analyze the complexity. Traversing all nodes of the tree takes O(n) time. However, adding the level list at the beginning of the result list and moving the rest behind takes O(n) time as well. So the overall time complexity is O(n^2).

A Better Solution:
Now that we know the time complexity is O(n^2), can we traverse the tree bottom-up, then append it to the array will takes only O(1) time thus the overall time complexity would be O(n). So far I was unabA Better Solution:
Now that we know the time complexity is O(n^2), can we traverse the tree bottom-up, then append it to the array will takes only O(1) time thus the overall time complexity would be O(n). 

So far I was unable to find a method to traverse the tree in level order bottom-up. It is hard to address the following tree
      1
     /  \
   2   3
        /  \
      15  7
If do the post-order traverse, it will start from 2 instead of 15. 

Iterative Solution:
The iterative solution for BFS is to use a queue. The idea is for each node, we enqueue all its left and right children into the queue, and dequeue all of them in next level. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            ArrayList<Integer> levelList = new ArrayList<Integer>();
            for (int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                levelList.add(curr.val);
                
                if (curr.left != null) {
                    queue.offer(curr.left);
                }
                if (curr.right != null) {
                    queue.offer(curr.right);
                }
            }
            result.add(0, levelList);
        }                      
        return result;
    }
} 

Summary:
Note the iterative solution of the BFS, be very familiar with the details. In addition, one possible O(n) solution for the bottom-up traversal is to do the top-down traversal first and get the final result list. Then reverse the list in-place. Since reversing the list takes O(n) time as well, the overall time complexity is still O(n). 

Leetcode: Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Understand of the problem:
The problem asks for finding the maximum depth of a binary tree. The maximum depth is defined as the number of nodes along the longest path from the root down to the farthest leaf node. 

Recursive Solution:
The idea is still using pre-order traversal. We keep tracking of the depth of each node, and if the node is a leaf, we compare its depth with the maximum depth, and update the maximum depth, if needed. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int max = Integer.MIN_VALUE;
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        
        maxDepth(root, 0);
        
        return max;
    }
    
    private void maxDepth(TreeNode root, int depth) {
        if (root == null) return;
        
        depth++;
        
        // check if it is leaf
        if (root.left == null && root.right == null && depth > max) {
            max = depth;
        }
        
        maxDepth(root.left, depth);
        maxDepth(root.right, depth);
    }
}

Post-order Traversal Solution:
So far I think we have been very familiar with the pre-order traversal. For this problem, we can also do the post-order traversal of the binary tree, i.e, traverse from bottom-up. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        
        return Math.max(left, right) + 1;
    }
}

Post-order Iterative Solution:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        
        int max = 0;
        Stack<TreeNode> nodeStack = new Stack<TreeNode>();
        Stack<Integer> depthStack = new Stack<Integer>();
        
        TreeNode prev = null;
        nodeStack.push(root);
        depthStack.push(1);
        
        while (!nodeStack.empty()) {
            TreeNode curr = nodeStack.peek();
            int depth = depthStack.peek();
            
            if (prev == null || curr == prev.left || curr == prev.right) {
                if (curr.left != null) {
                    nodeStack.push(curr.left);
                    depthStack.push(depth + 1);
                } else if (curr.right != null) {
                    nodeStack.push(curr.right);
                    depthStack.push(depth + 1);
                } else {
                    nodeStack.pop();
                    depthStack.pop();
                    if (depth > max) max = depth;
                }
            } else if (prev == curr.left) {
                if (curr.right != null) {
                    nodeStack.push(curr.right);
                    depthStack.push(depth + 1);
                } else {
                    nodeStack.pop();
                    depthStack.pop();
                    if (depth > max) max = depth;
                }
            } else if (prev == curr.right) {
                nodeStack.pop();
                depthStack.pop();
                if (depth > max) max = depth;
            }
            
            prev = curr;
        }
        return max;
    }
}

Summary:
The problem itself is very simple, but do be familiar with the post-order traversal. Especially be careful about the return value and how it works. 

Update on 9/30/14:
DFS solution:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int max = 0;
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        maxDepthHelper(root, 0);
        
        return max;
    }
    
    private void maxDepthHelper(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        
        depth++;
        
        if (root.left == null && root.right == null) {
            if (depth > max) {
                max = depth;
            }
            return;
        }
        
        maxDepthHelper(root.left, depth);
        maxDepthHelper(root.right, depth);
    }
}

Divide-and-Conquer

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        
        if (root == null) {
            return 0;
        }
        
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        
        return Math.max(left, right) + 1;
    }
}

Leetcode: Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Understand the problem:
The problem asks for finding the minimum depth of a binary tree. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. 

For example, given a binary tree:
      1
     /   \
   2    3
  /  \
4    5
The minimum depth is 2. 


Recursive Solution:
The recursive solution is similar to the path sum problem. We use preorder traversal of the binary tree. Each node accumulate the counter to present the depth of the node. If the node is a leaf, we compare it with the minimum value and update the minimum value. We recursively repeat this process until all nodes have been traversed. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int min = Integer.MAX_VALUE;
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        
        preOrderTraversal(root, 0);
        
        return min;
    }
    
    private void preOrderTraversal(TreeNode root, int depth) {
        if (root == null) return;
        
        depth++;
        
        // check if the node is leaf
        if (root.left == null && root.right == null && depth < min) {
            min = depth;
        }
            
        preOrderTraversal(root.left, depth);
        preOrderTraversal(root.right, depth);
    }
}

Iterative Solution:
The iterative solution is also very straightforward. The crux is to use two stacks, one stores the nodes, while the other store the depth of each node. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        
        Stack<TreeNode> nodeStack = new Stack<TreeNode>();
        Stack<Integer> depthStack = new Stack<Integer>();
        
        int min = Integer.MAX_VALUE;
        
        nodeStack.push(root);
        depthStack.push(1);
        
        while (!nodeStack.empty()) {
            TreeNode curNode = nodeStack.pop();
            int depth = depthStack.pop();
            
            // if it is a leaf node
            if (curNode.left == null && curNode.right == null && depth < min) {
                min = depth;
            }
            
            if (curNode.right != null) {
                nodeStack.push(curNode.right);
                depthStack.push(depth + 1);
            }
            
            if (curNode.left != null) {
                nodeStack.push(curNode.left);
                depthStack.push(depth + 1);
            }
        }
        
        return min;
    }
}

Summary:
The problem itself is straight-forward. The take-away message is to be careful the common ideas in tree-based problems. This question itself is very similar to the path sum problem. Be familiar with the ideas behind the solution.

Update on 12/16/14:

public class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        return minDepthHelper(root);
    }
    
    private int minDepthHelper(TreeNode root) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }
        
        if (root.left == null && root.right == null) {
            return 1;
        }
        
        return Math.min(minDepthHelper(root.left), minDepthHelper(root.right)) + 1; 
    }
}

Update on 4/7/15:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        return minDepthHelper(root);
    }
    
    private int minDepthHelper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int leftDepth = minDepthHelper(root.left);
        int rightDepth = minDepthHelper(root.right);
        
        if (leftDepth == 0 && rightDepth == 0) {
            return 1;
        }
        
        if (leftDepth == 0) {
            return rightDepth + 1;
        }
        
        if (rightDepth == 0) {
            return leftDepth + 1;
        }
        
        return Math.min(leftDepth, rightDepth) + 1;
    }
}

Update on 9/18/15:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        return minDepthHelper(root);
    }
    
    private int minDepthHelper(TreeNode root) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }
        
        int minLeft = minDepthHelper(root.left);
        int minRight = minDepthHelper(root.right);
        
        if (minLeft == Integer.MAX_VALUE && minRight == Integer.MAX_VALUE) {
            return 1;
        }
        
        return Math.min(minLeft, minRight) + 1;
    }
}

Leetcode: Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.


Understand the problem:

As described in the problem, given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. 

This question is similar to the last post where a sorted array is changed to a sorted linked list. The mainly challenge is to find the mid point of the linked list. This can be easily done by using two pointers. 

Solution:

The idea is still similar as the last post, where we were given a sorted array. So we first find the mid node of the linked list, partition to two lists, where the left list is the left subtree, and right part is the right subtree. We recursively repeat this process until the linked list become null. 

Code (Java):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedListToBST(ListNode head) {

        return toBST(head, null);
    }
    
    private TreeNode toBST(ListNode head, ListNode tail) {
        if (head == tail) return null;
        
        ListNode mid = findMid(head, tail);
        
        TreeNode root = new TreeNode(mid.val);
        
        root.left = toBST(head, mid);
        root.right = toBST(mid.next, tail);
        
        return root;
    }
    
    // Find the middle node of the linked list
    private ListNode findMid(ListNode head, ListNode tail) {
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != tail && fast.next != tail && fast.next.next != tail) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return slow;
    }
}

Discussion:
Note that in the recursive function we used a tail pointer points to the tail of the partitioned linked list. That is unusual for a linked list because we usually only track the head node of the list. In this problem, since we need to know the tail of the list, one method is to truncate the linked list. However, this solution has several drawbacks. First of all, it need to modify the linked list, which may not be desirable in practice. More important, we need to traverse the linked list again until the node before the mid node. Then set the next to null. It DOES NOT work just setting mid as null. Consider why the following code is wrong:

public class Solution {
    public TreeNode sortedListToBST(ListNode head) {

        return toBST(head);
    }
    
    private TreeNode toBST(ListNode head) {
        if (head == null) return null;
        
        ListNode mid = findMid(head);
        TreeNode root = new TreeNode(mid.val);
        
        // Terminate the left list
        ListNode rHead = mid.next;
        if (head == mid) {
            head = null;
        } else {
            mid = null;
        }
        
        root.left = toBST(head);
        root.right = toBST(rHead);
        
        return root;
    }
    
    // Find the middle node of the linked list
    private ListNode findMid(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return slow;
    }
}

That is because just setting mid as null does not modify the linked list at all. It only modify the mid pointer but the linked list remains the same. 

Now we analyze the complexity of this solution. Since finding the middle node takes O(n) time, the overall time complexity becomes O(n^2).  The space complexity is O(logn).

A Better Solution:
Note that in the previous solution the cost is on finding the middle node of the linked list, which takes O(n) time on average. If we can construct the tree in the order that we traverse the linked list, we don't need to jump back and forth to find the middle of the list.  Remember the inorder traversal of a binary tree, if it is a BST, the inorder traversal should be in ascending order. Can we do the reverse, i.e, given an sorted list, construct the BST inorder, i.e, from bottom-up? The answer is yes. 

Code (Java):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private ListNode p;
    public TreeNode sortedListToBST(ListNode head) {
        int len = getListLength(head);
        p = head;
        
        return toBST(0, len - 1);
    }
    
    private TreeNode toBST(int lo, int hi) {
        if (lo > hi) return null;
        
        int mid = (lo + hi)/2;
        
        TreeNode left = toBST(lo, mid - 1);
        
        TreeNode root = new TreeNode(p.val);
        p = p.next;
        
        TreeNode right = toBST(mid + 1, hi);
        
        root.left = left;
        root.right = right;
        
        return root;
    }
    
    private int getListLength(ListNode head) {
        ListNode p = head;
        int length = 0;
        
        while (p != null) {
            p = p.next;
            length++;
        }
        return length;
    }
}

Discussion:
Now the time complexity becomes O(n) since we traverse the linked list in order. 
Summary:
This post we learned how to convert a linked list to a BST. Note the linked list has no constant time in accessing a node, so we must build the tree from bottom up. Why we choose to traverse the tree in order, because the array is sorted and the inorder traversal can generate a BST.


Update on 10/7/14:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedListToBST(ListNode head) {

        return toBSTHelper(head);
    }
    
    private TreeNode toBSTHelper(ListNode head) {
        if (head == null) {
            return null;
        }
        
        if (head.next == null) {
            return new TreeNode(head.val);
        }
        
        // Find middle minus one node of the linked list
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null && fast.next.next != null && fast.next.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode mid = slow.next;
        TreeNode root = new TreeNode(mid.val);
        
        slow.next = null;
        
        root.left = toBSTHelper(head);
        root.right = toBSTHelper(mid.next);
        
        return root;
    }
}

Leetcode: Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.


Understand the problem:
As described in the problem, given an array sorted in ascending order, convert it to a balanced BST.

You must understand what is the height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Solution:
One idea is for a BST, the left children must be less than the parent, while the right children are greater than the parent. So following this idea, we could partition the array into two parts evenly. The middle point must be the parent, and the left part is less than the parent and must be the left children. The right part is greater than the middle and must be the right children. As a result, we divide the problem into two smaller sub-problems. We can recursively repeat this process until there is only one node for the left or right child. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
        if (num == null || num.length == 0) return null;
        
        return toBST(num, 0, num.length - 1);
    }
    
    private TreeNode toBST(int[] num, int lo, int hi) {
        if (lo > hi) return null;
        
        int mid = (lo + hi)/2;
        
        TreeNode root = new TreeNode(num[mid]);
        root.left = toBST(num, lo, mid - 1);
        root.right = toBST(num, mid + 1, hi);
        
        return root;
    }
}

Summary:
The problem is relatively straight-forward. The key idea is partition. Also, it is not hard to find that the idea is very similar to binary search. So we can see that it is very important to understand the basic data structure and algorithms. 

Leetcode: Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Understand the problem:
The problem asks for constructing a binary tree given inorder and postorder traversal of the tree. The problem is similar to the last post. So we can still use the same idea to construct a tree recursively.

Solution:
Since the last element of the post-order traversal must be the parent. So the value can partition the inorder array into two parts, the first part must be its left subtree, while the second part must be its right subtree. So now we partition the problem into two smaller problems, and we can recursively partition the list again until each subtree has only one element. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null || inorder.length == 0 || postorder.length == 0)
            return null;
        
        int len = inorder.length;
        return buildTree(inorder, 0, len - 1, postorder, 0, len - 1);
    }
    
    private TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int poStart, int poEnd) {
        if (inStart > inEnd) return null;
        
        int rootVal = postorder[poEnd];
        int rootIdx = 0;
        
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                rootIdx = i;
                break;
            }
        }
        
        TreeNode root = new TreeNode(rootVal);
        int len = rootIdx - inStart;
        
        root.left = buildTree(inorder, inStart, rootIdx - 1, postorder, poStart, poStart + len - 1);
        root.right = buildTree(inorder, rootIdx + 1, inEnd, postorder, poStart + len, poEnd - 1);
        
        return root;
    }
}

FOLLOW-UP
Given a preorder and postorder of a tree, can we construct the binary tree?
The answer is NO. We must need an inorder traversal to construct the tree. That is because 
the order of the inorder traversal is left child -> parent -> right child. So given a parent node, we can easily partition the list into left subtree and right subtree. But given only preorder and postorder traversal, there is no way to partition the list. 

Summary:
In this post, we learned how to construct a binary tree from its inorder and postorder traversal. The key idea is using recursion. It is the key to solve this kind of questions.

Leetcode: Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Understand the problem:

The problem gives two arrays, which represent the preorder and inorder traversal of the binary tree. Construct the binary tree according to the two traversals. 

We can use several examples to better understand the problem.  For a tree

              1

            /    \

          2     3

         /   \

       4     5

The preorder traversal is 1, 2, 4, 5, 3
The inorder traversal is 4, 2, 5, 1, 3

Solution:
The solution is based on the idea of preorder traversal. For a given arrays of preorder traversal and inorder traversal, the first node of the preorder array must be the root value, then we can divide the inorder array into two parts according to the value in the first node of the preorder traversal. The left part must be its left subtree, while the right part must be its right subtree. Then we divide the problem into smaller question, and repeat the above operations until there is only one node for each side.

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0)
            return null;
        
        int len = preorder.length;
        
        return buildTree(preorder, 0, len - 1, inorder, 0, len - 1);
    }
    
    private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (inStart > inEnd) {
            return null;
        }
        
        int rootVal = preorder[preStart];
        int rootIdx = 0;
        
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                rootIdx = i;
                break;
            }
        }
        int len = rootIdx - inStart;
        TreeNode root = new TreeNode(rootVal);
        
        // recursively call its left and right subtree
        root.left = buildTree(preorder, preStart + 1, preStart + len, inorder, inStart, rootIdx - 1);
        root.right = buildTree(preorder, preStart + len + 1, preEnd, inorder, rootIdx + 1, inEnd);
        
        return root;
    }
}

Summary:
This question is relatively tricky in Leetcode. The key idea is to partition the two lists into sublists, and recursively solve the problem. Be careful the recursive solutions in tree-based questions. It is extremely useful. 

Leetcode: Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

Understand the problem:
As described by the problem, this question is quite similar to the Path Sum I. The mainly difference is it returns all nodes in the path.

Recursive Solution:
The recursive solution is similar to Path Sum I, but saved the traversed node. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> nodes = new ArrayList<Integer>();
        
        preOrderTraversal(root, 0, sum, result, nodes);
        
        return result;
    }
    
    private void preOrderTraversal(TreeNode root, int pathSum, int sum, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> nodes) {
        if (root == null) return;
        
        nodes.add(root.val);
        pathSum += root.val;
        
        // root is leaf
        if (root.left == null && root.right == null && pathSum == sum) {
            result.add(nodes);
        }
        
        preOrderTraversal(root.left, pathSum, sum, result, new ArrayList<Integer>(nodes));
        preOrderTraversal(root.right, pathSum, sum, result, new ArrayList<Integer>(nodes));
    }
}

Discussion:
Note in the line 30 and 31, you should create a new object. That is because Java object is passed by "reference" (although this is not a correct statement; everything in Java is passed by value).  In this case, each node maintains a separated partial list. 

Iterative Solution:
The iterative solution utilized three stacks. One stores the nodes, the second stack stores the path sum, while the third one stores the partial array list. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (root == null) return result;
        
        Stack<TreeNode> nodeStack = new Stack<TreeNode>();
        Stack<Integer> sumStack = new Stack<Integer>();
        Stack<ArrayList<Integer>> listStack = new Stack<ArrayList<Integer>>();
        
        nodeStack.push(root);
        sumStack.push(root.val);
        ArrayList<Integer> tempList = new ArrayList<Integer>();
        tempList.add(root.val);
        listStack.push(tempList);
        
        while (!nodeStack.empty()) {
            TreeNode currNode = nodeStack.pop();
            int pathSum = sumStack.pop();
            ArrayList<Integer> list = listStack.pop();
            
            // leaf
            if (currNode.left == null && currNode.right == null && pathSum == sum) {
                result.add(list);
            }
            
            if (currNode.right != null) {
                nodeStack.push(currNode.right);
                sumStack.push(currNode.right.val + pathSum);
                ArrayList<Integer> temp = new ArrayList<Integer>(list);
                temp.add(currNode.right.<Integer> temp = new ArrayList<Integer>(list);
                temp.add(cal);
                listStack.push(temp);
            }
            
            if (currNode.left != null) {
                nodeStack.push(currNode.left);
                sumStack.push(currNode.left.val + pathSum);
                ArrayList<Integer> temp = new ArrayList<Integer>(list);
                temp.add(currNode.left.val);
                listStack.push(temp);
            }
        }
        return result;
    }
}

Update on 10/7/14:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>>result = new ArrayList<List<Integer>>();
        if (root == null) {
            return result;
        }
        
        List<Integer> curList = new ArrayList<Integer>();
        pathSumHelper(root, sum, 0, curList, result);
        
        return result;
    }
    
    private void pathSumHelper(TreeNode root, int sum, int curSum, List<Integer> curList, List<List<Integer>> result) {
        if (root == null) {
            return;
        }
        
        curSum += root.val;
        curList.add(root.val);
        
        if (root.left == null && root.right == null && curSum == sum) {
            result.add(new ArrayList(curList));
            curList.remove(curList.size() - 1);
            return;
        }
        
        pathSumHelper(root.left, sum, curSum, curList, result);
        pathSumHelper(root.right, sum, curSum, curList, result);
        curList.remove(curList.size() - 1);
    }
}

A clear solution:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null) {
            return result;
        }
        
        List<Integer> curList = new ArrayList<Integer>();
        pathSumHelper(root, sum, 0, curList, result);
        
        return result;
    }
    
    private void pathSumHelper(TreeNode root, int sum, int curSum, List<Integer> curList, List<List<Integer>> result) {
        if (root == null) {
            return;
        }I
        
        curSum += root.val;
        curList.add(root.val);
        
        if (root.left == null && root.right == null && curSum == sum) {
            result.add(new ArrayList<Integer>(curList));
            //curList.remove(curList.size() - 1);
        }
        
        if (root.left != null) {
            pathSumHelper(root.left, sum, curSum, curList, result);
            curList.remove(curList.size() - 1);
        }
        
        if (root.right != null) {
            pathSumHelper(root.right, sum, curSum, curList, result);
            curList.remove(curList.size() - 1);
        }
    }
}

Update on 11/7/2014:
A better iterative solution:

public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        
        if (root == null) {
            return result;
        }
        
        Stack<TreeNode> nodeStack = new Stack<TreeNode>();
        Stack&l;tInteger> levelStack = new Stack<Integer>();
        
        int[] path = new int[1000];
        
        nodeStack.push(root);
        levelStack.push(0);
        
        while (!nodeStack.isEmpty()) {
            TreeNode currNode = nodeStack.pop();
            int level = levelStack.pop();
            path[level] = currNode.val;
            
            if (currNode.left == null && currNode.right == null) {
                int curSum = 0;
                List<Integer> temp = new ArrayList<Integer>();
                for (int i = 0; i < level + 1; i++) {
                    curSum += path[i];
                    temp.add(path[i]);
                }
                if (curSum == sum) {
                    result.add(temp);
                }
            }
            
            if (currNode.right != null) {
                nodeStack.push(currNode.right);
                levelStack.push(level + 1);
            }
            
            if (currNode.left != null) {
                nodeStack.push(currNode.left);
                levelStack.push(level + 1);
            }
        }
        return result;
    }
}

Update on 4/14/15:
An iterative solution without using a path array. It is naturally an corresponding iterative solution of the recursive one. 

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null) {
            return result;
        }
        
        Stack<TreeNode> nodeStack = new Stack<TreeNode>();
        Stack<Integer> levelStack = new Stack<Integer>();
        
        List<Integer> curList = new ArrayList<Integer>();
        
        nodeStack.push(root);
        levelStack.push(1);
        
        int curSum = 0;
        
        while (!nodeStack.isEmpty()) {
            TreeNode curNode = nodeStack.pop();
            int curLevel = levelStack.pop();
            curSum += curNode.val;
            
            // remove list elements
            while (curList.size() >= curLevel) {
                curSum -= curList.get(curList.size() - 1);
                curList.remove(curList.size() - 1);
            }
            
            curList.add(curNode.val);
            
            // if is a leaf node
            if (curNode.left == null && curNode.right == null && curSum == sum) {
                result.add(new ArrayList<Integer>(curList));
            }
            
            if (curNode.right != null) {
                nodeStack.push(curNode.right);
                levelStack.push(curLevel + 1);
            }
            
            if (curNode.left != null) {
                nodeStack.push(curNode.left);
                levelStack.push(curLevel + 1);
            }
        }
        return result;
    }
}