[LeetCode] Recover Binary Search Tree

Thought: Recursion way is trivial.

Code:

public class Solution {

    public static TreeNode previous, first, second;

    public void recoverTree(TreeNode root) {

        previous = null;

        first = null;

        second = null;

        inorder(root);   

        swap(first, second);

    }

    public void inorder(TreeNode root) {

        if (root == null) return;

        if (root.left != null) inorder(root.left);

        dosomething(root);

        if (root.right != null) inorder(root.right);

    }

    public void dosomething(TreeNode root) {

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

            if (first == null) {

                first = previous;

                second = root;

            }else second = root;

        }

        previous = root;

    }

    public void swap(TreeNode first, TreeNode second) {

        int temp = first.val;

        first.val = second.val;

        second.val = temp;

    }

}

Note: There exists a smart traversal method -> Inorder Morris Traversal 
No Recursion, no stack!!!
   
 public void inorder(TreeNode root) {
        if (root == null) return;
        TreeNode cur = root;
        while (cur != null) { 
            if (cur.left == null) { // no left child -> visit and step right
                dosomething(cur);
                cur = cur.right;
            }else {
                TreeNode tmp = cur.left; 
                while (tmp.right != null && tmp.right != cur) { // let tmp step rightest
                    tmp = tmp.right;
                }
                if (tmp.right == null) { // tmp is leaf -> build circle and step left
                    tmp.right = cur;
                    cur = cur.left;
                }else {
                    tmp.right = null; // tmp is already in circle -> destroy circle, visit, and step right
                    dosomething(cur);
                    cur = cur.right;
                }
            }
        }

    }

[LeetCode] Populating Next Right Pointers in Each Node

Thought:
Recursion.

Code:
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) return;
        if (root.left != null) root.left.next = root.right;
        if (root.right != null) root.right.next = root.next != null ? root.next.left : null;
        connect(root.left);
        connect(root.right);            
    }
}

Thought: using a Level Order Traversal will be more clear and common.

Code:
public void connect(TreeLinkNode root) {
        if (root == null) return;
        Queue<TreeLinkNode> q1 = new LinkedList<TreeLinkNode>();
        Queue<Integer> q2 = new LinkedList<Integer>();
        q1.offer(root);
        q2.offer(1);
        while (!q1.isEmpty()) {
            TreeLinkNode current = q1.poll();
            int level = q2.poll();
            if (q2.peek() != null && q2.peek() == level) {
                current.next = q1.peek();
            }
            //do something with current
            if (current.left != null) {
                q1.offer(current.left);
                q2.offer(level + 1);
            }
            if (current.right != null) {
                q1.offer(current.right);
                q2.offer(level + 1);
            }
        }

    }

[LeetCode] Validate Binary Serach Tree

Thought:
Check whether the root is in specific range.

Code:
public class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    public boolean helper(TreeNode root, int min, int max) {
        if (root == null) return true;
        if (root.val >= max || root.val <= min) return false;
        return helper(root.left, min, root.val) && helper(root.right, root.val, max);
    }
}

[LeetCode] Unique Binary Search Trees II

Thought:
Recursion.

Code:
public class Solution {
    public ArrayList<TreeNode> generateTrees(int n) {
        return generateBST(1,n);
    }
    public ArrayList<TreeNode> generateBST(int start, int end){
        ArrayList<TreeNode> result = new ArrayList<TreeNode>();
        if(start>end){
            result.add(null);
        }else if(start==end){
            result.add(new TreeNode(start));
        }else{
            for(int i=start;i<=end;i++){                
                ArrayList<TreeNode> left = generateBST(start,i-1); 
                ArrayList<TreeNode> right = generateBST(i+1,end);
                for(int k = 0;k<left.size();k++){
                    for(int j = 0;j<right.size();j++){ 
                        TreeNode root = new TreeNode(i);
                        root.left = left.get(k);
                        root.right = right.get(j);
                        result.add(root);
                    }
                }
            }
        }        
        return result; 
    }
}

[LeetCode] Unique Binary Search Trees

Thought:
Recursion. We could also use DP to do faster.

Code:
public class Solution {
    public int numTrees(int n) {
        if (n < 2) return 1;
        if (n == 2) return 2;
        int result = 0;
        for (int i = 0; i < n; i++) {
            result = result + numTrees(i) * numTrees(n - i - 1);
        }
        return result;      
    }
}

[LeetCode] Permutations

Thought:
Recursion.

Code:
public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> cache = new ArrayList<Integer>();
        if (num.length == 1) {
            cache.add(num[0]);
            result.add(cache);
            return result;
        }       
        int first = num[0];
        int[] previous = Arrays.copyOfRange(num, 1, num.length);
        ArrayList<ArrayList<Integer>> temp = permute(previous);
        for (ArrayList<Integer> list : temp) {
            for (int i = 0; i <= list.size(); i++) {
                list.add(i, first);
                result.add(new ArrayList<Integer>(list));
                list.remove(i);
            }
        }
        return result;
    }
}

[CTCI 4th Edition] 8.7

Given an infinite number of quarters, dimes, nickels and pennies, write code to calculate the number of ways of representing n cents.

Thought:
f(n, number, base) : to represent n cents using number of base.
g(n) = f(n, 0, 25) + f(n, 1, 25) +....
       = f(n, 0, 10) + f(n, 1, 10) +... + f(n-25, 0, 10) + f(n-25, 1, 10)+...

[LeetCode] N Queen II

Thought:
It is much easier than the previous problem.

Code:
public class Solution {
    int[] cache;
    int result;
    public int totalNQueens(int n) {
        cache = new int[n];
        result = 0;
        placeQueen(0, n);
        return result;
    }
    public boolean check(int row) {
        for (int i = 0; i < row; i++) {
            int dif = Math.abs(cache[i] - cache[row]);
            if (dif == 0 || dif == row - i) return false;
        }
        return true;
    }
    public void placeQueen(int row, int max) {
        if (row == max) {           
            result++;
            return;
        }
        for (int i = 0; i < max; i++) {
            cache[row] = i;
            if (check(row)) placeQueen(row + 1, max);
        }
    }
}

[LeetCode] N Queen

Thought:
It is a classic backtracking problem.
Cache stores the column index of each queen in each row.
Check method check the rules of queens.
We first put the first queen in the first row, and if no rules violated, we put the next row, once we have put N queens, update the result.

Code:
public class Solution {
    int[] cache;
    ArrayList<String[]> result;
    public ArrayList<String[]> solveNQueens(int n) {
        cache = new int[n];
        result = new ArrayList<String[]>();
        placeQueen(0, n);
        return result;
    }
    public boolean check(int row) {
        for (int i = 0; i < row; i++) {
            int dif = Math.abs(cache[i] - cache[row]);
            if (dif == 0 || dif == row - i) return false;
        }
        return true;
    }
    public void placeQueen(int row, int max) {
        if (row == max) {           
            String[] buffer = new String[max];
            for (int i = 0; i < max; i++) {
                StringBuilder temp = new StringBuilder();
                for (int j = 0; j < max; j++) {
                    if (cache[i] == j) temp.append("Q");
                    else temp.append(".");
                }
                buffer[i] = temp.toString();
            }
            result.add(buffer);
            return;
        }
        for (int i = 0; i < max; i++) {
            cache[row] = i;
            if (check(row)) placeQueen(row + 1, max);
        }
    }
}

[LeetCode] Symmetric Tree

Thought:
Recursion.

Code:
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }else {
            return symmetric(root.left, root.right);
        }
    }
    public boolean symmetric(TreeNode n1, TreeNode n2){
        if (n1 == null && n2 == null) {
            return true;
        }else{
            return n1 != null && n2 != null && n1.val == n2.val && symmetric(n1.left,n2.right) && symmetric(n1.right,n2.left);
        }
    }
}

[LeetCode] Search Insert Position

Thought:
It is actually finding how many numbers are smaller than target.

Code:
public class Solution {
    public int searchInsert(int[] A, int target) {
        return helper(A, target, 0, A.length - 1);
    }
    public int helper(int[] A, int target, int start, int end) {   
        if (start >= end) return A[start] >= target ? 0 : 1;
        int mid = (start + end) / 2;
        if (A[mid] == target) return mid - start;
        if (A[mid] > target) return helper(A, target, start, mid - 1);
        return mid - start + 1 + helper(A, target, mid + 1, end);
    }
}

[LeetCode] Same Tree

Thought:
Basic Recursion.

Code:
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

[LeetCode] Path Sum

Thought:
Recursion.

Code:
public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        if (root.left == null && root.right == null) return (root.val == sum);
        return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val);
    }
}

[LeetCode] Pascal's Triangle

Thought:
Basically the same with the previous problem.

Code:
public class Solution {
    public ArrayList<ArrayList<Integer>> generate(int numRows) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < numRows; i++){
            result.add( getRow(i) );
        }
        return result;   
    }
    public ArrayList<Integer> getRow(int rowIndex) {
        if ( rowIndex < 0 ){
            return null;
        }else{
            if( rowIndex == 0 ){
                ArrayList<Integer> result = new ArrayList<Integer>();
                result.add(1);
                return result;
            }else{
                ArrayList<Integer> result = getRow(rowIndex-1);
                result.add(1);
                for(int i = rowIndex-1; i>0; i--){
                    result.set(i, result.get(i) + result.get(i-1));
                }
                result.set(0,1);
                return result;
            }
        }           
    }
}

[LeetCode] Pascal's Triangle II

Thought:
Calculate from the end to the front.

Code:
public class Solution {
    public ArrayList<Integer> getRow(int rowIndex) {
        if (rowIndex == 0) {
            ArrayList<Integer> result = new ArrayList<Integer>();
            result.add(1);
            return result;
        }else {
            ArrayList<Integer> result = getRow(rowIndex - 1);
            result.add(1);
            for (int i = rowIndex - 1; i > 0; i--) {
                result.set(i, result.get(i) + result.get(i - 1));
            }
            result.set(0,1);
            return result;
        }
    }
}

[LeetCode] Merge k Sorted Lists

Thought:
Basically, we could merge every list into the first, the complexity will be nl1 + (n-1)l2 + ... + 1*ln;
To be faster, we could merge the first and the last, recursively. The complexity will be lgn*(l1 + l2 + ... + ln).
Using randomization, we could cancel out the difference between l1 - ln.
So the first method will result in the time O(n^2), while the second one is O(nlgn).

Code 1:
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists.size() == 0) return null;
        for (int i = 1; i < lists.size(); i++) {
            lists.set(0, mergeTwoLists(lists.get(0), lists.get(i)));
        }
        return lists.get(0);
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }else {           
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }    
    }
}

Code 2:
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        int len = lists.size();
        if (len == 0) return null;
        int start = 0;
        int end = len - 1;
        while (len > 1) {
            lists.set(start, mergeTwoLists(lists.get(start), lists.get(end)));
            start++;
            end--;
            if (start >= end) {
                len = (len + 1) / 2;
                start = 0;
                end = len - 1;
            }
        }
        return lists.get(start);
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }else {           
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }    
    }
}

[LeetCode] Merge Two Sorted Lists

Thought:
Recursion.

Code:
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }else {           
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }    
    }
}

[LeetCode] Minimum Depth of Binary Tree

Thought:
Recursion.

Code:
public class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null) return minDepth(root.right) + 1;
        if (root.right == null) return minDepth(root.left) + 1;
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
}

[LeetCode] Maximum Depth of Binary Tree

Thought:
What's the problem....

Code:
public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        else return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

[LeetCode] Flatten Binary Tree to Linked List

Thought:
Recursion, after flatten the left subtree and the right subtree, we should do some small adjustment.

Code:
public class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        else if (root.left == null && root.right == null) return;
        else {
            flatten(root.left);
            flatten(root.right);
            TreeNode flag = root.left;
            if (flag != null) { 
                while (flag.right != null) {
                    flag = flag.right;            
                }
                flag.right = root.right;
                root.right = root.left;
                root.left = null;
            }
        }
    }
}