Copy List with Random Pointer @LeetCode

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.

	package leetcode;
	import java.util.Random;
	/**
	* Problem: 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:
	* We can't copy them from head to rear because there's no node when we copy random pointer.
	* 1. We can copy the a node after original node. there're double nodes after copyNext.
	* 2. Then copy random. head.next.random = head.random.next. Take care of situation random = null. need to judge.
	* 3. Split the list into two same list.
	*
	* My Thought.
	* 1. head.next.random != null. --> no need. but as they may be null, null pointer problem exist. (I didn't understand problem)
	* 2. newNode.random = head.random --> no need. We need to findout if the node's random is null.
	* Codes needs to be changed like this. if (head.random != null) in copyRandom. works but not straightforward like following.
	*
	*
	* TestCase:
	* Random Pointer could be null
	*
	*
	* @author jeffwan
	* @date Feb 27, 2014
	*/
	public class CopyRandomList {
	public RandomListNode copyRandomList(RandomListNode head) {
	if (head == null) {
	return null;
	}
	copyNext(head);
	copyRandom(head);
	return splitList(head);
	}
	public void copyNext(RandomListNode head) {
	while (head != null) {
	RandomListNode newNode = new RandomListNode(head.label);
	newNode.next = head.next;
	newNode.random = head.random;
	head.next = newNode;
	head = head.next.next;
	}
	}
	public void copyRandom(RandomListNode head) {
	while (head != null) {
	if (head.next.random != null) {
	head.next.random = head.random.next;
	}
	head = head.next.next;
	}
	}
	public RandomListNode splitList(RandomListNode head) {
	RandomListNode newHead = head.next;
	while (head != null) {
	RandomListNode temp = head.next;
	head.next = temp.next;
	head = head.next;
	if (temp.next != null) {
	temp.next = temp.next.next;
	}
	}
	return newHead;
	}
	}
	class RandomListNode {
	int label;
	RandomListNode next, random;
	RandomListNode(int x) {this.label = x; }
	}

view raw CopyRandomList.java hosted with ❤ by GitHub

Sum Root to Leaf Numbers @LeetCode

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.

	package leetcode.combinations;
	import java.util.ArrayList;
	/**
	*
	* Solution: This problem is similar to PathSum II.
	* Condition: when goes to leaf code, calculate number and add to sum.
	* We call use different ways to calculate number. ArrayList is one option.
	*
	* The logic could also be written like this, much more clear. but I like my version more. -- keep same to PathSum II.
	* number.add(root.val);
	* if (root.left == null && root.right == null) {
	* sum += getValue(number);
	* } else {
	* helper(sum, number, root.left);
	* helper(sum, number, root.right);
	* }
	* number.remove(number.size() - 1);
	*
	* Take care: We cannot put sum into helper parameter list, as helper has no return value, sum will only change in sub function!
	* After functions return, sum is still that sum! remove sum in parameter and declare it as class variable outside functions.
	* I made this fault in Convert Sorted List to height balanced BST
	*
	* @author jeffwan
	* @date Feb 16, 2014
	*/
	public class SumNumbers {
	int sum = 0;
	public int sumNumbers(TreeNode root) {
	if (root == null) {
	return 0;
	}
	ArrayList<Integer> list = new ArrayList<Integer>();
	helper(root, list);
	return sum;
	}
	private void helper(TreeNode root, ArrayList<Integer> list) {
	if (root == null) {
	return;
	}
	if (root.left == null && root.right == null) {
	list.add(root.val);
	sum += getValue(list);
	list.remove(list.size() - 1);
	return;
	}
	list.add(root.val);
	helper(root.left, list);
	helper(root.right, list);
	list.remove(list.size() - 1);
	}
	private int getValue(ArrayList<Integer> list) {
	int value = 0;
	for (int i = 0; i < list.size(); i++) {
	value = value * 10 + list.get(i);
	}
	return value;
	}
	private static class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int x) { this.val = x; }
	}
	}

view raw SumNumbers.java hosted with ❤ by GitHub

Linked List Cycle II @LeetCode

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

	package leetcode.linkedlist;
	/***
	* To be honest, I cannot infer this by mySelf. Just remember the answer.
	*
	* Solution 1: Two meets.
	* After first meet, head and slow move together, next time, that means second time, they meet at Entry.
	*
	* Solution 2: Three meets.
	* After first meet, let slow go and meet fast again, then we get the circle length L.
	* Let them go back head, let one go L steps, and the third time we meet will at Entry.
	*
	* Reference: http://blog.csdn.net/whuwangyi/article/details/14103993 && CC 150
	*
	* @author jeffwan
	* @date Feb 16, 2014
	*/
	public class DetectCycle {
	public ListNode detectCycle(ListNode head) {
	if (head == null) {
	return null;
	}
	ListNode slow, fast;
	slow = fast = head;
	do {
	if (fast.next == null || fast.next.next == null) {
	return null;
	}
	slow = slow.next;
	fast = fast.next.next;
	} while(slow != fast);
	while(head != slow) {
	head = head.next;
	slow = slow.next;
	}
	return head;
	}
	class ListNode {
	int val;
	ListNode next;
	ListNode (int x) { this.val = x; }
	}
	}

view raw DetectCycle.java hosted with ❤ by GitHub

Linked List Cycle @LeetCode

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

	package leetcode.linkedlist;
	import java.util.Hashtable;
	/**
	* Solution:
	* 1.If has cycle in list, fast will catch up slow finally(fast == slow).
	* 2.If not, will never. Fast will go the end at first (fast.next == null || fast.next.next == null)
	*
	* Extra Space Solution:
	* Use Hashtable stores pointer, if contains same key --> cycle.(how to code in java? we can't)
	*
	* There're two kind of cycle. hashtable can handle these two.
	*
	* @author jeffwan
	* @date Feb 16, 2014
	*/
	public class HasCycle {
	public boolean hasCycle(ListNode head) {
	if (head == null) {
	return false;
	}
	ListNode fast = head;
	ListNode slow = head;
	do {
	if(fast == null || fast.next == null) {
	return false;
	}
	slow = slow.next;
	fast = fast.next.next;
	} while(fast != slow);
	return true;
	}
	class ListNode {
	int val;
	ListNode next;
	ListNode (int x) { this.val = x; }
	}
	}

view raw HasCycle.java hosted with ❤ by GitHub

Merge Two Sorted Lists @LeetCode

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

	package leetcode.linkedlist;
	/**
	* Solution: Better to create a dummy node as first node which makes works easier.
	* Just simple problem, no algorithm in it. Take care of some details and make codes clean.
	*
	* @author jeffwan
	* @date Feb 16, 2014
	*/
	public class MergeTwoLists {
	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
	ListNode dummy = new ListNode(0);
	ListNode head = dummy;
	while(l1 != null && l2 != null) {
	if (l1.val <= l2.val) {
	head.next = l1;
	l1 = l1.next;
	} else {
	head.next = l2;
	l2 = l2.next;
	}
	head = head.next;
	}
	if (l1 != null) {
	head.next = l1;
	}
	if (l2 != null) {
	head.next = l2;
	}
	return dummy.next;
	}
	class ListNode {
	int val;
	ListNode next;
	ListNode (int x) {
	this.val = x;
	}
	}
	}

view raw MergeTwoLists.java hosted with ❤ by GitHub

Partition List @LeetCode

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

	package leetcode.linkedlist;
	/**
	* Solution: Split list into two list, one's value < x, one's >= x. and the merge two List together.
	* All three methods are same, little difference in coding.
	*
	* @author jeffwan
	* @date Feb 16, 2014
	*/
	public class Partition {
	/**
	* Solution1: Dummy Node -- very ingenious method.
	* 1. Only need left, right as end pointer, start pointer use Dummy node.
	* 2. Don't forget right.next = null. becuase the last right node may not the last node in orginal list.
	*
	* 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5.
	* Why 1 2 2 4 3 5 but not 1 2 2 3 4 5. left < x, right >=x, and We must keep preserve original order.
	*/
	public ListNode partition(ListNode head, int x) {
	if (head == null) {
	return null;
	}
	ListNode leftDummy = new ListNode(0);
	ListNode rightDummy = new ListNode(0);
	ListNode left = leftDummy, right = rightDummy;
	while (head != null) {
	if (head.val < x) {
	left.next = head;
	left = left.next;
	} else {
	right.next = head;
	right = right.next;
	}
	head = head.next;
	}
	right.next = null; // important
	left.next = rightDummy.next;
	return leftDummy.next;
	}
	/**
	* Solution2: Split into two list and each with start pointer and then merge.
	* LeetCode Online judge says Answer wrong, because I insert every node in the head. the sequence is not ascending order.
	* But it really works.
	*/
	public ListNode partition2(ListNode head, int x) {
	if (head == null || head.next == null) {
	return head;
	}
	ListNode beforeStart = null;
	ListNode afterStart = null;
	while(head != null) {
	ListNode next = head.next;
	if (head.val < x) {
	head.next = beforeStart;
	beforeStart = head;
	} else {
	head.next = afterStart;
	afterStart = head;
	}
	head = next;
	}
	if (beforeStart == null) {
	return afterStart;
	}
	head = beforeStart;
	while(beforeStart.next != null) {
	beforeStart = beforeStart.next;
	}
	beforeStart.next = afterStart;
	return head;
	}
	/**
	* Solution3: same to Solution2, split into two list and each with start and end pointer. this one could AC on LeetCode.
	* Don't forget head.next = null!!! cut the list node!
	* Solution2 don't need to cut because it insert in the head.
	*/
	public ListNode partition3(ListNode head, int x) {
	ListNode beforeStart = null;
	ListNode beforeEnd = null;
	ListNode afterStart = null;
	ListNode afterEnd = null;
	while (head != null) {
	ListNode next = head.next;
	head.next = null;
	if (head.val < x) {
	if (beforeStart == null) {
	beforeStart = head;
	beforeEnd = head;
	} else {
	beforeEnd.next = head;
	beforeEnd = beforeEnd.next;
	}
	} else {
	if (afterStart == null) {
	afterStart = head;
	afterEnd = head;
	} else {
	afterEnd.next = head;
	afterEnd = afterEnd.next;
	}
	}
	head = next;
	}
	if (beforeStart == null) {
	return afterStart;
	}
	beforeEnd.next = afterStart;
	return beforeStart;
	}
	class ListNode {
	int val;
	ListNode next;
	ListNode (int x) {
	this.val = x;
	}
	}
	}

view raw Partition.java hosted with ❤ by GitHub

Remove Duplicates from Sorted List II @LeetCode

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

	package leetcode.linkedlist;
	/**
	* Solution: Use Dummy Node to handle the head change.
	*
	* Difference between II and I is the head will not change even duplicates in I, but will change in II(remove all same).
	* So we need dummy node to delete head node, In addition, we need to remember the value of duplicate node.
	* Usually, only head changes, we use dummy node. We can't change dummy in progress, because it points to head we will return at last.
	*
	* Take care:
	* int val = head.next.val must use while delete this value at once.
	* head = head.next must be wrapped by else, or it may head.next == null, and next loop. null.next leads NullPointer Problem.
	* This is not same as removeduplicate I, while condition is not same.
	*
	*
	* @author jeffwan
	* @date Feb 16, 2014
	*/
	public class DeleteDuplicates2 {
	public ListNode deleteDuplicates(ListNode head) {
	if (head == null || head.next == null) {
	return head;
	}
	ListNode dummy = new ListNode(0);
	dummy.next = head;
	head = dummy;
	while (head.next != null && head.next.next != null) {
	if (head.next.val == head.next.next.val) {
	int val = head.next.val;
	while (head.next != null && head.next.val == val) {
	head.next = head.next.next;
	}
	} else {
	head = head.next;
	}
	}
	return dummy.next;
	}
	class ListNode {
	int val;
	ListNode next;
	ListNode (int x) {
	this.val = x;
	}
	}
	}

view raw DeleteDuplicates2.java hosted with ❤ by GitHub

Path Sum @LeetCode

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

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

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

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

	package leetcode.combinations;
	/**
	* Solution: Divide & Conquer, same as PathSum II, if sum == 0, return retur, other false.
	* Take care: Although return false in if() doesn't matter, if it's not written, still write, but low inefficiency,
	* need to write it.
	*
	* I am not sure if this is strict Divide & Conquer, because it's not a sub tree problem, just one-way, the main var is sum
	*
	* @author jeffwan
	* @date Feb 15, 2014
	*/
	public class HasPathSum {
	public boolean hasPathSum(TreeNode root, int sum) {
	if (root == null) {
	return false;
	}
	sum -= root.val;
	if (root.left == null && root.right == null) {
	if (sum == 0) {
	return true;
	}
	return false;
	}
	// Divide
	boolean leftResult = hasPathSum(root.left, sum);
	boolean rightResult = hasPathSum(root.right, sum);
	// Conquer
	return leftResult || rightResult;
	}
	private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int x) { this.val = x; }
	}
	}

view raw HasPathSum.java hosted with ❤ by GitHub

Path Sum II @LeetCode

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]
]

	package leetcode.combinations;
	import java.util.ArrayList;
	/**
	* Solution: DFS Traversal + Combination
	* Use sum with traversal to implement to target -- What I think is use another sum += root.val, but obviously,
	* it's more complicated than sum -= root.val;
	*
	* @author jeffwan
	* @date Feb 15, 2014
	*/
	public class PathSum {
	public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	ArrayList<Integer> list = new ArrayList<Integer>();
	helper(result, list, root, sum);
	return result;
	}
	private void helper(ArrayList<ArrayList<Integer>> result,
	ArrayList<Integer> list, TreeNode root, int sum) {
	if (root == null) {
	return;
	}
	sum -= root.val;
	if (root.left == null && root.right == null) {
	if (sum == 0) {
	list.add(root.val);
	result.add(new ArrayList<Integer>(list));
	list.remove(list.size() - 1);
	}
	return;
	}
	list.add(root.val);
	helper(result, list, root.left, sum);
	helper(result, list, root.right, sum);
	list.remove(list.size() - 1);
	}
	private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int x) { this.val = x; }
	}
	}

view raw pathSum.java hosted with ❤ by GitHub

Remove Duplicates from Sorted List @LeetCode

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

	package leetcode.linkedlist;
	import java.util.Hashtable;
	import javax.swing.text.html.HTMLDocument.RunElement;
	/**
	* Solution: One pointer - Solution 3, Two pointer(with runner) - Solution 1 (same to 3, only use runner replace current.next)
	*
	* @author jeffwan
	* @date Mar 7, 2014
	*/
	public class DeleteDuplicates {
	/**
	* Solution1:Two pointer, Iterative way. two while loops. one current, one runner. still O(n)
	* Remember to return head but not current, current already go to last node.
	* @param head
	* @return
	*/
	public ListNode deleteDuplicates(ListNode head) {
	if (head == null) {
	return null;
	}
	ListNode current = head;
	ListNode runner = head.next;
	while(runner != null) {
	if (runner.val == current.val) {
	current.next = runner.next;
	} else {
	current = runner;
	}
	runner = runner.next;
	}
	return head;
	}
	/**
	* Solution2: Single Pointer
	* This way is almost same to remove duplicates from sorted List II(with dummy node).
	* Only difference is we start from current, use current.next = current.next.next to skip current.next
	*
	* Actually, for this problem, solution1 seems more straightforward.
	*/
	public ListNode deleteDuplicates2(ListNode head) {
	if (head == null || head.next == null) {
	return head;
	}
	ListNode current = head;
	while (current!= null && current.next != null) {
	if(current.val == current.next.val) {
	int val = current.val;
	while(current.next != null && current.next.val == val) {
	current.next = current.next.next;
	}
	}
	current = current.next;
	}
	return head;
	}
	/**
	* Solution 3: Single Pointer -- Best solution I think.
	* Actually, we could use this ways directly but not solution2. Because we don't need to remember to target value.
	* Solution 4 is useless, we just need to campare with head.val, no need to use a map.
	* @param head
	* @return
	*/
	public ListNode deleteDuplicates3(ListNode head) {
	if (head == null || head.next == null) {
	return head;
	}
	ListNode newHead = head;
	while (head.next != null) {
	if (head.next.val == head.val) {
	head.next = head.next.next;
	} else {
	head = head.next;
	}
	}
	return newHead;
	}
	/**
	* Solution4: Extra Space - Hashtable -- complier error in LeetCode Online Judge but really works.
	* @param head
	* @return
	*/
	public ListNode deleteDuplicates4(ListNode head) {
	if(head == null) {
	return null;
	}
	ListNode current = head;
	Hashtable table = new Hashtable();
	table.put(current.val, true);
	while (current.next != null) {
	if (table.containsKey(current.next)) {
	current.next = current.next.next;
	} else {
	table.put(current.next.val, true);
	current = current.next;
	}
	}
	return current;
	}
	class ListNode {
	int val;
	ListNode next;
	ListNode (int x) {
	this.val = x;
	}
	}
	}

view raw DeleteDuplicates.java hosted with ❤ by GitHub

Construct Binary Tree from Inorder and Postorder Traversal @LeetCode

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

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

	package leetcode.tree;
	/**
	* Solution:
	* postorder: 4 1 3 10 (left) 11 8 2 (right) 7
	* inorder: 4 10 3 1 (left) 7 11 8 2 (right)
	*
	* Same as Preorder - Inorder Construction. Only difference is sequence and index handling.
	*
	* @author jeffwan
	* @date Feb 14, 2014
	*/
	public class InPostBuildTree {
	public TreeNode buildTree(int[] inorder, int[] postorder) {
	if (inorder == null || postorder == null || inorder.length == 0 || postorder.length == 0 ||
	inorder.length != postorder.length) {
	return null;
	}
	int inorderLength = inorder.length;
	int postorderLength = postorder.length;
	return helper(inorder, postorder, 0, inorderLength - 1, 0, postorderLength - 1);
	}
	private TreeNode helper(int[] inorder, int[] postorder, int inStart, int inEnd, int postStart, int postEnd) {
	if (inStart > inEnd) {
	return null;
	}
	int rootIndex = 0;
	int rootValue = postorder[postEnd];
	TreeNode root = new TreeNode(rootValue);
	for (int i = inStart; i <= inEnd; i++) {
	if (inorder[i] == rootValue) {
	rootIndex = i;
	break;
	}
	}
	int length = rootIndex - inStart;
	// Divide & Conquer
	root.left = helper(inorder, postorder, inStart, rootIndex - 1, postStart, postStart + length - 1);
	root.right = helper(inorder, postorder, rootIndex + 1, inEnd, postStart + length, postEnd - 1);
	return root;
	}
	// TreeNode
	public class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode (int x) {
	val = x;
	}
	}
	}

view raw InPostBuildTree.java hosted with ❤ by GitHub

Construct Binary Tree from Preorder and Inorder Traversal @LeetCode

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

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

	package leetcode.tree;
	/**
	* Solution:
	* preorder: 7 10 4 3 1 (left) 2 8 11 (left)
	* inorder: 4 10 3 1 (left) 7 11 8 2 (right)
	*
	* 1. the first node in preorder must be root
	* 2. find out root position in inorder, and then root.left will be left part, same as root.right.
	* 3. Preorder: root, root.left, root.right --> (preStart+1, prestart+Index-inStart) will be left part, the rest are right part.
	* 4. do left subtree as 1-3, recursively.
	*
	* This is just a binary tree, not BST!
	*
	* Reference: http://leetcode.com/2011/04/construct-binary-tree-from-inorder-and-preorder-postorder-traversal.html
	*
	* @author jeffwan
	* @date Feb 14, 2014
	*/
	public class InPreBuildTree {
	public TreeNode buildTree(int[] preorder, int[] inorder) {
	if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0
	|| preorder.length != inorder.length) {
	return null;
	}
	int preorderLength = preorder.length;
	int inorderLength = inorder.length;
	return helper(preorder, inorder, 0, preorderLength - 1, 0, inorderLength - 1);
	}
	private TreeNode helper(int[] preorder,int[] inorder,int preStart,int preEnd,int inStart,int inEnd) {
	if (inStart > inEnd) {
	return null;
	}
	int rootIndex = 0;
	int rootValue = preorder[preStart];
	TreeNode root = new TreeNode(rootValue);
	for (int i = inStart; i <= inEnd; i++) {
	if (inorder[i] == rootValue) {
	rootIndex = i;
	break;
	}
	}
	int length = rootIndex - inStart;
	root.left = helper(preorder, inorder, preStart + 1, preStart + length, inStart, rootIndex - 1);
	root.right = helper(preorder, inorder, preStart + length + 1, preEnd, rootIndex + 1, inEnd);
	return root;
	}
	// TreeNode
	private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode (int x) {
	val = x;
	}
	}
	}

view raw InPreBuildTree.java hosted with ❤ by GitHub

Convert Sorted List to Binary Search Tree @LeetCode

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

	package leetcode.tree;
	/**
	* @author jeffwan
	* @date Feb 13, 2014
	*/
	public class SortedListToBST {
	/**
	* Solution 1: Bottom-up approach. We can't easily find out the middle node of List, so we'd like to get node,
	* insert, and get next node. Still concludes Binary Search & Divide Conquer thought in it.
	*
	* Take care:
	* 1. I past head into traversal like traversal(0, length - 1). Come on! this is not C with pointer,
	* after if finished and return back, head will not change in right subtree. We must declare a var outside functions.
	*
	* 2. The BinarySearch according to length of list make sure the tree data structure. like level!
	* Only parent get the value of head.val, so head.next == null only happens at last step(we don't need to care about that)
	*
	* 2. We got different balanced BST using this method and array(SortedArrayToBST). That's possible. No big deal.
	* Balanced BST may have different types especially few nodes.
	*
	* 3 5 8 9 10 List Array
	*
	* 9 8
	* 5 10 3 9
	* 3 8 5 10
	*
	* Reference: http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html
	*/
	//
	ListNode listNode;
	public TreeNode sortedListToBST(ListNode head) {
	if (head == null) {
	return null;
	}
	int length = 0;
	ListNode count = head;
	while (count != null) {
	length++;
	count = count.next;
	}
	listNode = head;
	return traversal(0, length - 1);
	}
	private TreeNode traversal (int start, int end) {
	if (start > end) {
	return null;
	}
	int mid = start + (end - start) / 2;
	// Divide
	TreeNode left = traversal(start, mid - 1);
	TreeNode parent = new TreeNode(listNode.val);
	listNode = listNode.next;
	TreeNode right = traversal(mid + 1, end);
	// Conquer
	parent.left = left;
	parent.right = right;
	return parent;
	}
	private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int x) { val = x; }
	}
	}

view raw SortedListToBST.java hosted with ❤ by GitHub

Convert Sorted Array to Binary Search Tree @LeetCode

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

	package leetcode.tree;
	public class SortedArrayToBST {
	/**
	* Thought: In order to make it height BST, we can not insert node into tree from int[0].
	* The problem is how to determine the root node --> middle. which makes left and right have same count nodes or +1.
	*
	* Use Binary Search thought to solve this problem. Difference is node take num[mid], so we need to change the index
	* mid-1 and mid+1, what's more, start > end works but not start + 1 >= end. return null means leaf.left == null
	*
	* After we solve the root problem, the left subtree will be same problem. --> Divide & Conquer
	*
	* like 1 2 3 4 5 6 7 8 -- balanced
	*
	* 4
	* 2 6
	* 1 3 5 7
	* 8
	*
	* Reference: http://leetcode.com/2010/11/convert-sorted-array-into-balanced.html
	*
	* @param num
	* @return
	*/
	public TreeNode sortedArrayToBST(int[] num) {
	if (num == null || num.length == 0) {
	return null;
	}
	return helper(num, 0, num.length - 1);
	}
	private TreeNode helper(int[] num, int start, int end) {
	if (start > end) {
	return null;
	}
	// Binary Search Thought
	int mid = start + (end - start) / 2;
	TreeNode node = new TreeNode(num[mid]);
	// Divide
	node.left = helper(num, start, mid - 1);
	node.right = helper(num, mid + 1, end);
	// Conquer
	return node;
	}
	// TreeNode
	private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode (int x) {
	val = x;
	}
	}
	}

view raw SortedArrayToBST.java hosted with ❤ by GitHub

Recover Binary Search Tree @LeetCode

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

	package leetcode.tree;
	/**
	* Thought: Use inorder traversal --> make it as a increasing array, so the problem convert to find two swap points
	* in a increasing array.
	*
	* 1 2 3 4 5 6 --> 1 5 3 4 2 6 in right array, lastNode.val < root.val should always be true
	* lastNode.val > root.val means there's bad points location there, 1st, lastNode. 2nd, root.
	* 5 5
	* 2 7 7 2 7 > 5 > 2 because we use inorder, so lastNode.val > root.val. --> bad point. 1.lastNode 2.root
	* Don't forget move forward lastNode!
	*
	* In addition, o(n) solution. inOrderTraversal and reassign values.
	*
	* @author jeffwan
	* @date Feb 13, 2014
	*/
	public class RecoverTree {
	private TreeNode firstNode = null;
	private TreeNode secondNode = null;
	private TreeNode lastNode = new TreeNode(Integer.MIN_VALUE);
	public void recoverTree(TreeNode root) {
	// Find out two bad points
	traversal(root);
	// Swap value of two points
	int temp = firstNode.val;
	firstNode.val = secondNode.val;
	secondNode.val = temp;
	}
	private void traversal(TreeNode root) {
	if (root == null) {
	return;
	}
	traversal(root.left);
	if (firstNode == null && lastNode.val > root.val) {
	firstNode = lastNode;
	}
	if (firstNode != null && lastNode.val > root.val) {
	secondNode = root;
	}
	lastNode = root;
	traversal(root.right);
	}
	// TreeNode
	public class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode (int x) {
	val = x;
	}
	}
	}

view raw RecoverTree.java hosted with ❤ by GitHub

Binary Tree Zigzag Level Order Traversal @LeetCode

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

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

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

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

	package leetcode.tree;
	import java.util.ArrayList;
	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.Stack;
	/**
	* Solution1: Two Stack.
	* 这边reverse 时候正好利用了stack的特性, 第一遍添加的时候，从left -> right, 读出来正好是reverse的，然后normalOrder = false,
	* 先添加right child. 再加上stack，反反为正.
	* 因为没有queue.size() 那么方便来控制level，只能用两个stack了，另外一定注意，move Depth时候，要给nextLevel新的空间，否则
	* nextLevel push的时候，currLevel指向同一空间，这样!currLevel.isEmpty.直接就全部读完了.
	*
	* Solution2: Almost same to levelOrder I. Queue + list.add(index, E);
	* Only difference is to reverse element in even number. so we use a flag here.
	* Every line, flag++, and then use % 2 to see it's odd or even level.
	*
	* @author jeffwan
	* @date Feb 12, 2014
	*/
	public class ZigzagLevelOrder {
	public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	if (root == null) {
	return result;
	}
	Stack<TreeNode> currLevel = new Stack<TreeNode>();
	Stack<TreeNode> nextLevel = new Stack<TreeNode>();
	currLevel.push(root);
	boolean normalOrder = true;
	while (!currLevel.isEmpty()) {
	ArrayList<Integer> level = new ArrayList<Integer>();
	while (!currLevel.isEmpty()) {
	TreeNode current = currLevel.pop();
	level.add(current.val);
	if (normalOrder) {
	if (current.left != null) {
	nextLevel.push(current.left);
	}
	if (current.right!= null) {
	nextLevel.push(current.right);
	}
	} else {
	if (current.right!= null) {
	nextLevel.push(current.right);
	}
	if (current.left != null) {
	nextLevel.push(current.left);
	}
	}
	}
	result.add(level);
	// Notice we need to give nextLevel a new space to prevent error from pointing to same space with currLevel
	currLevel = nextLevel;
	nextLevel = new Stack<TreeNode>();
	normalOrder = !normalOrder;
	}
	return result;
	}
	public ArrayList<ArrayList<Integer>> zigzagLevelOrder2(TreeNode root) {
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	if (root == null) {
	return result;
	}
	Queue<TreeNode> queue = new LinkedList<TreeNode>();
	queue.offer(root);
	int flag = 1;
	while (!queue.isEmpty()) {
	ArrayList<Integer> level = new ArrayList<Integer>();
	int queueSize = queue.size();
	for (int i = 0; i < queueSize; i++) {
	TreeNode node = queue.poll();
	if (flag % 2 == 1) {
	level.add(node.val);
	} else {
	level.add(0, node.val);
	}
	if (node.left != null) {
	queue.offer(node.left);
	}
	if (node.right != null){
	queue.offer(node.right);
	}
	}
	flag++;
	result.add(level);
	}
	return result;
	}
	// TreeNode
	private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode (int x) {
	val = x;
	}
	}
	}

view raw ZigzagLevelOrder.java hosted with ❤ by GitHub

Binary Tree Level Order Traversal II @LeetCode

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],
]

	package leetcode.tree;
	import java.util.ArrayList;
	import java.util.LinkedList;
	import java.util.Queue;
	/**
	* Thought: Almost same to levelOrder BFS I.
	*
	* Only difference is result.add(0, level); every time, we add the next level to top of result.
	* Use LinkedList add(inddex, element);
	*
	* @author jeffwan
	* @date Feb 12, 2014
	*/
	public class LevelOrderBottom {
	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()) {
	ArrayList<Integer> level = new ArrayList<Integer>();
	int queueSize = queue.size();
	for (int i = 0; i < queueSize; i++) {
	TreeNode node = queue.poll();
	level.add(node.val);
	if (node.left != null) {
	queue.offer(node.left);
	}
	if (node.right != null) {
	queue.offer(node.right);
	}
	}
	result.add(0, level);
	}
	return result;
	}
	// TreeNode
	private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode (int x) {
	val = x;
	}
	}
	}

view raw LevelOrderBottom.java hosted with ❤ by GitHub

Binary Tree Level Order Traversal @LeetCode

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

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

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

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

	package leetcode.tree;
	import java.util.ArrayList;
	import java.util.LinkedList;
	import java.util.Queue;
	/**
	* Thought: Use Queue to store every layer nodes, the most important is to terminate level. we use queue size.
	*
	* 1. int queueSize = queue.size(), we cannot put queue.size() in for loop as it will changes in loop.
	* 2. Queue is just a interface, we use LinkedList as implement class.
	* 3. Must judge if root == null, or NullPointerProblem in list.add(node.val). return result instead of null -- coding style.
	* Extension: Except this way, any other ways?
	* 1. Queue + dummyNode --> insert dummyNode when one line ends. dummyNode has No meaning like Integer.MAX_VALUE
	* 2. Two Queue --> next time, we stored in another queue, for loop ends until size of current queue size==0.
	*
	* Actually, our ways is the best way (use quese size to control line).
	*
	* @author jeffwan
	* @date Feb 12, 2014
	*/
	public class LevelOrder {
	public ArrayList<ArrayList<Integer>> levelOrder(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()) {
	ArrayList<Integer> level = new ArrayList<Integer>();
	int queueSize = queue.size();
	for (int i = 0 ; i < queueSize; i++) {
	TreeNode node = queue.poll();
	level.add(node.val);
	if (node.left != null) {
	queue.offer(node.left);
	}
	if (node.right != null) {
	queue.offer(node.right);
	}
	}
	result.add(level);
	}
	return result;
	}
	// TreeNode
	private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode (int x) {
	val = x;
	}
	}
	}

view raw LevelOrder.java hosted with ❤ by GitHub

Lastest Common Ancester

Find the Latest Common Ancestor of two TreeNode.
For Example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

 The LCA of 3 and 4 is 2. 5 and 6 is 5.

	package leetcode.tree;
	import java.util.ArrayList;
	public class LatestCommonAncestor {
	/**
	* Thought:
	* 1. Get parent node until root.
	* 2. find the node1 and node2 in left and right subtree. if found, return node and go up. if not found,
	* that means in the another(left / right) tree;
	* 3. Conclude scenario two nodes in one line, will return the first directly.
	*/
	public TreeNode lastCommonAncestor(TreeNode node1, TreeNode node2) {
	if (node1 == null || node2 == null) {
	return null;
	}
	TreeNode root = getRoot(node1);
	return getChild(root, node1, node2);
	}
	private TreeNode getRoot(TreeNode node) {
	while (node.parent != null) {
	node = node.parent;
	}
	return node;
	}
	public TreeNode getChild(TreeNode root, TreeNode node1, TreeNode node2) {
	if (root == null || root == node1 || root == node2) {
	return root;
	}
	// Divide
	TreeNode left = getChild(root.left, node1, node2);
	TreeNode right = getChild(root.right, node1, node2);
	// Conquer
	if (left != null && right != null) {
	return root;
	}
	if (left != null) {
	return left;
	}
	if (right != null) {
	return right;
	}
	return null;
	}
	/**
	* Thought: very straightforwards
	* 1. getPath2Root --> get every node's Path to Root and saved as a list.
	* 2. iterative and find out when they are different which means that node is their latest common ancestor
	*
	* Take care:
	* 1. iterative must begin from end to start. if reverse, as length may be different, can find the common one.
	* 2. if two nodes are on one line, will not return in for, then i or j == -1, return i+1 last one. which will be common.
	*
	*/
	public TreeNode lastCommonAncestor2(TreeNode node1, TreeNode node2){
	ArrayList<TreeNode> list1 = getPath2Root(node1);
	ArrayList<TreeNode> list2 = getPath2Root(node2);
	int i, j;
	for (i=list1.size() - 1, j = list2.size() - 1; i >= 0 && j >= 0; i--,j--) {
	if (list1.get(i) != list2.get(j)) {
	return list1.get(i).parent;
	}
	}
	return list1.get(i+1);
	}
	public ArrayList<TreeNode> getPath2Root(TreeNode node) {
	ArrayList<TreeNode> list = new ArrayList<TreeNode>();
	while (node != null) {
	list.add(node);
	node = node.parent;
	}
	return list;
	}
	// TreeNode
	private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode parent;
	TreeNode (int x) {
	val = x;
	}
	}
	}

view raw LatestCommonAncestor.java hosted with ❤ by GitHub

Binary Tree Maximum Path Sum @LeetCode

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

	package leetcode.tree;
	/**
	* Thought: check every subtree to findout the maxPath, then go upstair.
	*
	* singlePath = Math.max(left.singlePath, right.singlePath) + root.val --> find out the MaxPath of last two layer TreeNode.
	* maxPath = Math.max(left.maxPath, right.maxPath) --> find out the maxPath of left and right subtree
	*
	* maxPath = Math.max(maxPath, left.singlePath + right.singlePath + root.val); negative condition already in.
	* --> if subtree is larger than leftsinglePath + rightsinglePath, will not cross root, like follows
	* 4 + 2 + 5 > 7 + 1 + 3 --> maxPath will be 4 --> 2 --> 5, if 3 replaces 5, maxPath will be 4 --> 2 --> 1 --> 3
	*
	* 1
	* 2 3
	* 4 5
	*
	* Take care: there may be negative weight TreeNode, there's will be more conditions.
	* Condition: singlePath = Math.max(singlePath, 0); --> if single path sum less than 0, abort
	*
	*
	*
	* @author jeffwan
	* @date Feb 12, 2014
	*/
	public class MaxPathSum {
	public int maxPathSum(TreeNode root) {
	ResultType result = helper(root);
	return result.maxPath;
	}
	private ResultType helper(TreeNode root) {
	if(root == null) {
	return new ResultType(0, Integer.MIN_VALUE);
	}
	// divide
	ResultType left = helper(root.left);
	ResultType right = helper(root.right);
	// conquer
	int singlePath = Math.max(left.singlePath, right.singlePath) + root.val;
	singlePath = Math.max(singlePath, 0);
	int maxPath = Math.max(left.maxPath, right.maxPath);
	maxPath = Math.max(maxPath, left.singlePath + right.singlePath + root.val);
	return new ResultType(singlePath, maxPath);
	}
	private class ResultType {
	int singlePath;
	int maxPath;
	ResultType(int singlePath, int maxPath) {
	this.singlePath = singlePath;
	this.maxPath = maxPath;
	}
	}
	// TreeNode
	private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode (int x) {
	val = x;
	}
	}
	}

view raw MaxPathSum.java hosted with ❤ by GitHub

Balanced Binary Tree @LeetCode

Given a binary tree, determine if it is height-balanced.

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.

	package leetcode.tree;
	/**
	* Thought: Check left and right tree, campare their maxPath, if > 1, not balanced.
	*
	* left == -1 means the child is already not balanced
	* right == -1
	*
	* if (Math.abs(left - right)) > 1 must contains condition left == -1 and right == -1
	* Or, return -1 compare with 0, return 0, test case as follows.
	* 1
	* 1 1
	* 1 1
	* 1 1
	*
	* @author jeffwan
	* @date Feb 11, 2014
	*/
	public class IsBalanced {
	public boolean isBalanced (TreeNode root) {
	return maxDepth(root) != -1;
	}
	private int maxDepth(TreeNode root) {
	if (root == null) {
	return 0;
	}
	int left = maxDepth(root.left);
	int right = maxDepth(root.right);
	if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
	return -1;
	}
	return Math.max(left, right) + 1;
	}
	// TreeNode
	private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode (int x) {
	val = x;
	}
	}
	}

view raw IsBalanced.java hosted with ❤ by GitHub

Maximum Depth of Binary Tree @LeetCode

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.

	package leetcode.tree;
	/**
	* Classic Practice of Divide & Conquer
	* @author jeffwan
	* @date Feb 11, 2014
	*/
	public class MaxDepth {
	/**
	* Though: maxDepth == Max(left, right) + 1.
	*/
	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;
	}
	// TreeNode
	private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode (int x) {
	val = x;
	}
	}
	}

view raw MaxDepth.java hosted with ❤ by GitHub

Flatten Binary Tree to Linked List @LeetCode

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Hints:

If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

	package leetcode.tree;
	import java.util.LinkedList;
	import leetcode.tree.InorderTraversal.TreeNode;
	public class FlatternBinaryTreeToLinkedList {
	/**
	* Solution1: Tree Reconstruct -- Handle left Tree, then hanlde right tree.
	* Except first time, lastNode will not be null, everytime,
	* lastNode.left == null ---> cut down left tree
	* lastNode.right == root ---> move left tree to right node.(will not miss right,
	* because right tree already stored in previous recursion)
	* lastNode = root --> move depth
	*
	* Take Care: remember to store right tree, or when flatten(right), right tree will not original one
	*
	*/
	public TreeNode lastNode = null;
	public void flatten(TreeNode root) {
	if (root == null) {
	return;
	}
	if (lastNode != null) {
	lastNode.left = null;
	lastNode.right = root;
	}
	lastNode = root;
	TreeNode right = root.right;
	flatten(root.left);
	flatten(right);
	}
	/**
	* Solution2: Travesal
	* My though: It's a preorderTraversal, So I can traversal all tree nodes, and sotres in a LinkedList,
	* So this LinkedList can meets need. But we still need to convert this Tree.
	*
	* Defect: need to reconstruct -- poor efficiency
	* @param root
	*/
	public void flatten2(TreeNode root) {
	LinkedList<TreeNode> list = new LinkedList<TreeNode>();
	TreeNode node = root;
	traversal(list, node);
	// ReConstruct this Tree
	for (int i=1; i< list.size(); i++) {
	root.left = null;
	root.right = list.get(i);
	root = root.right;
	}
	}
	private void traversal(LinkedList list, TreeNode node) {
	if (node == null) {
	return;
	}
	list.add(node);
	traversal(list, node.left);
	traversal(list, node.right);
	}
	// TreeNode
	private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode (int x) {
	val = x;
	}
	}
	}

view raw FlatternBinaryTreeToLinkedList.java hosted with ❤ by GitHub

Combination Sum II @LeetCode

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8, 
A solution set is: 
[1, 7] 
[1, 2, 5] 
[2, 6] 
[1, 1, 6] 

	package leetcode.combinations;
	import java.util.ArrayList;
	import java.util.Arrays;
	/**
	* Almost same as CombinationSum I, Only difference is element can only used in combination once.
	* As there're duplicate elements, we need to make sure result with no duplidates like subsets II.
	*
	* Element used once --> helper(xxx, i+1)
	* Result without duplicates --> if(i!=position && num[i] == nums[i-1]) { continue; }
	*
	* i!=position --> only happens when backtrack, after move number1. number2 cannot be used.
	* i==position --> just add number2, not iterative it. (We don't allow number2 iteration which number1 already does)
	*
	* @author jeffwan
	* @date Feb 11, 2014
	*/
	public class CombinationSum2 {
	public static void main(String[] args) {
	int[] nums = {10, 1, 2, 7, 6, 1, 5};
	int target = 8;
	System.out.println(combinationSum2(nums,target));
	}
	public static ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
	Arrays.sort(num);
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	ArrayList<Integer> list = new ArrayList<Integer>();
	combinationSumHelper(result, list, num, target, 0);
	return result;
	}
	private static void combinationSumHelper(ArrayList<ArrayList<Integer>> result,
	ArrayList<Integer> list, int[] num, int target, int position) {
	int sum = 0;
	for (int x: list) {
	sum += x;
	}
	if (sum == target) {
	result.add(new ArrayList<Integer>(list));
	return;
	}
	if (sum < target) {
	for (int i = position; i<num.length; i++) {
	if ( i != position && num[i] == num[i-1]) {
	continue;
	}
	list.add(num[i]);
	combinationSumHelper(result, list, num, target, i+1);
	list.remove(list.size() - 1);
	}
	}
	}
	}

view raw CombinationSum2.java hosted with ❤ by GitHub

Combination Sum @LeetCode

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7, 
A solution set is: 
[7] 
[2, 2, 3] 

	package leetcode.combinations;
	import java.util.ArrayList;
	import java.util.Arrays;
	/**
	* Thought: Same as subsets, condition is sum == target, if sum < target, go recursion
	* The most importance is the next number should be gotten from current i, so, helper(xxx, i) but not i+1,
	* i + 1 can not get the same number.
	*
	* In addition: remember to sort the int array at first!!!
	*
	* @author jeffwan
	* @date Feb 11, 2014
	*/
	public class CombinationSum {
	public static void main(String args[]) {
	int[] candidates = {8, 7, 4, 3};
	int target = 11;
	System.out.println(combinationSum(candidates, target));
	}
	public static ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
	Arrays.sort(candidates);
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	ArrayList<Integer> list = new ArrayList<Integer>();
	combinationSumHelper(result, list, candidates, target, 0);
	return result;
	}
	private static void combinationSumHelper(ArrayList<ArrayList<Integer>> result,
	ArrayList<Integer> list, int[] candidates, int target, int position) {
	int sum = 0;
	for (int x: list) {
	sum += x;
	}
	if (sum == target) {
	result.add(new ArrayList<Integer>(list));
	return;
	}
	if (sum < target) {
	for (int i = position; i < candidates.length; i++) {
	list.add(candidates[i]);
	combinationSumHelper(result, list, candidates, target, i);
	list.remove(list.size() - 1);
	}
	}
	}
	}

view raw CombinationSum.java hosted with ❤ by GitHub

Letter Combinations of a Phone Number @LeetCode

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

	package leetcode.combinations;
	import java.util.ArrayList;
	/**
	* Character.getNumericValue("23".charAt(0)); --> Get int value From different digit of string
	* Difference from subsets --- not just one array.
	*
	* Solution: use index to control char group -- useful
	* Because char in every group is unique, we don't need flag position to control ordering like other combination problems.
	* We only need to care how to map in differnt groups, we use sb.toString() here.
	* sb.toString() = 0, get index 0 of digits, --> 2, so select char[2] group.
	*
	* We could also use Hashmap instead of char[][]
	*
	* @author jeffwan
	* @date Feb 10, 2014 Refactor April.10
	*/
	public class LetterCombinations {
	char[][] map = {{}, {}, {'a','b','c'}, {'d','e','f'}, {'g','h','i'}, {'j','k','l'}, {'m','n','o'},
	{'p','q','r','s'}, {'t','u','v'}, {'w','x','y','z'}};
	public ArrayList<String> letterCombinations(String digits) {
	ArrayList<String> result = new ArrayList<String>();
	StringBuffer sb = new StringBuffer();
	helper(result, sb, digits);
	return result;
	}
	private void helper(ArrayList<String> result, StringBuffer sb,
	String digits) {
	if (sb.length() == digits.length()) {
	result.add(sb.toString());
	return;
	}
	int index = Character.getNumericValue(digits.charAt(sb.length()));
	for (int i = 0; i < map[index].length; i++) {
	sb.append(map[index][i]);
	helper(result, sb, digits);
	sb.deleteCharAt(sb.length() - 1);
	}
	}
	/**
	Map<Character, char[]> map = new HashMap<Character, char[]>();
	map.put('0', new char[] {});
	map.put('1', new char[] {});
	map.put('2', new char[] { 'a', 'b', 'c' });
	map.put('3', new char[] { 'd', 'e', 'f' });
	map.put('4', new char[] { 'g', 'h', 'i' });
	map.put('5', new char[] { 'j', 'k', 'l' });
	map.put('6', new char[] { 'm', 'n', 'o' });
	map.put('7', new char[] { 'p', 'q', 'r', 's' });
	map.put('8', new char[] { 't', 'u', 'v'});
	map.put('9', new char[] { 'w', 'x', 'y', 'z' });
	for (char c : map.get(digits.charAt(sb.length()))) {
	sb.append(c);
	helper(map, digits, sb, result);
	sb.deleteCharAt(sb.length() - 1);
	}
	*/
	}

view raw LetterCombinations.java hosted with ❤ by GitHub

Implement strStr() @LeetCode

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

	package leetcode.simpleCoding;
	/**
	* @date Feb 8, 2014
	*
	* Test case: (1123 123) ("","") --> may OutOfBound ,("a","a") --> s1.length()- s2.length()+1 not without +1, bound check.
	* return value: haystack.subString(i) but not String.valueOf(i) ("","" will return 0).
	* take care
	*/
	public class StrStr {
	public static void main(String args[]) {
	String haystack = "a";
	String needle = "a";
	System.out.println(strStr(haystack, needle));
	}
	public static String strStr(String haystack, String needle) {
	if (haystack == null || needle == null) {
	return null;
	}
	int i,j = 0;
	for (i = 0; i < haystack.length() - needle.length() + 1; i++) {
	for (j = 0; j<needle.length(); j++) {
	if (haystack.charAt(i + j) != needle.charAt(j)) {
	break;
	}
	}
	if (j == needle.length()) {
	return haystack.substring(i);
	}
	}
	return null;
	}
	}

view raw StrStr.java hosted with ❤ by GitHub

Permutations II @LeetCode

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

	package leetcode.combinations;
	import java.util.ArrayList;
	import java.util.Arrays;
	/**
	* Thought: Almost same as Permutation. Only difference is to remove duplicates.
	* if number1 equals number2, defaultly, we get the number1, abort number2, so
	* number2 can't be used if the number1 haven't be used.
	*
	* In subset, we have a position marker and sorted int array. As we don't have position now, we could
	* use a flag array instead.
	*
	* @author jeffwan
	* @date Feb 10, 2014
	*/
	public class Permutations2 {
	public static void main(String[] args) {
	int[] num = {1, 1, 2};
	System.out.println(permuteUnique(num));
	}
	public static ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
	Arrays.sort(num);
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	ArrayList<Integer> list = new ArrayList<Integer>();
	boolean[] visited = new boolean[num.length];
	permuteUniqueHelper(result, list, num, visited);
	return result;
	}
	private static void permuteUniqueHelper(ArrayList<ArrayList<Integer>> result,
	ArrayList<Integer> list, int[] num, boolean[] visited) {
	if (list.size() == num.length) {
	result.add(new ArrayList<Integer>(list));
	return;
	}
	for (int i=0; i<num.length; i++) {
	if (visited[i]==true || (i!=0 && num[i] == num[i-1] && visited[i-1] == false)) {
	continue;
	}
	visited[i] = true;
	list.add(num[i]);
	permuteUniqueHelper(result, list, num, visited);
	list.remove(list.size() - 1);
	visited[i] = false;
	}
	}
	}

view raw Permutations2.java hosted with ❤ by GitHub

Permutations @LeetCode

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

	package leetcode.combinations;
	import java.util.ArrayList;
	import java.util.Arrays;
	/**
	* Problem: How to make it as Permutation according to combination?
	* -- don't use position as start marker. Help only has three parameters.
	*
	* Every time we can get other element from whole int[],start from 0, so i=0, just need to remove duplicate
	*
	* if list.size() == num.length, we add a result and return, Actually, remove return; will not have influence on final result.
	* the program will slow because it will enter following loop until go out.
	* (Every time it contains, and continue because of full of different elements stored already)
	*
	* In addition, we remove Arrays.sort(num) because permutation don't care non-descending order.
	*
	* @author jeffwan
	* @date Feb 10, 2014
	*/
	public class Permutations {
	public ArrayList<ArrayList<Integer>> permute(int[] num) {
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	ArrayList<Integer> list = new ArrayList<Integer>();
	permuteHelper(result, list, num);
	return result;
	}
	private void permuteHelper(ArrayList<ArrayList<Integer>> result,
	ArrayList<Integer> list, int[] num) {
	if (list.size() == num.length) {
	result.add(new ArrayList<Integer>(list));
	return;
	}
	for (int i = 0; i < num.length; i++) {
	if (list.contains(num[i])) {
	continue;
	}
	list.add(num[i]);
	permuteHelper(result, list, num);
	list.remove(list.size() - 1);
	}
	}
	}

view raw Permutations.java hosted with ❤ by GitHub

Subsets II @LeetCode

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

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

For example,
If S = [1,2,2], a solution is:

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

	package leetcode.combinations;
	import java.util.ArrayList;
	import java.util.Arrays;
	/**
	*
	* @author jeffwan
	* @date Feb 10, 2014
	*
	* Thought -- number2 can't selected before number1, i>=position.abort number2 when i> position
	*
	* Almost same to subset I, only difference is if() to skip the duplicate
	* i == position --> go depth, when we add number, we don't care duplicates
	* i != position means back tracking, already remove one number, i++ which leads i!=position,(i>position also works)
	* that means second or third or more time, we care about the duplicate numbers. As they are sorted, we abort and continue.
	*
	*/
	public class Subsets2 {
	public static void main(String[] args) {
	int[] S = {1, 2, 2, 2};
	System.out.println(subsetsWithDup(S));
	}
	public static ArrayList<ArrayList<Integer>> subsetsWithDup (int[] num) {
	Arrays.sort(num);
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	ArrayList<Integer> list = new ArrayList<Integer>();
	subsetsWithDupHelper(result, list, num, 0);
	return result;
	}
	private static void subsetsWithDupHelper(ArrayList<ArrayList<Integer>> result,
	ArrayList<Integer> list, int[] num, int position) {
	result.add(new ArrayList<Integer>(list));
	for (int i = position; i < num.length; i++) {
	if (i != position && num[i] == num[i-1]){
	continue;
	}
	list.add(num[i]);
	subsetsWithDupHelper(result, list, num, i+1);
	list.remove(list.size() - 1);
	}
	}
	}

view raw Subsets2.java hosted with ❤ by GitHub

Subsets @LeetCode

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

Note:

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

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

	package leetcode.combinations;
	import java.util.ArrayList;
	import java.util.Arrays;
	/**
	* @author jeffwan
	* @date Feb 10, 2014
	*
	* All combination and Permutations problems should be converted to search problems.
	* Thought -- DFS and BackTracking. Add a number, and go depth until the last number, and then back track.
	* Take care:result.add(list) --> result.add(new ArrayList<Integer>(list)), if use the previous,
	* result will also change because of the changes of list in ever loop. It need a new space every time.
	*
	* position -- mark start position, all elements should be gotten larger than position.
	* So that's why subsets(x,x,x,i+1) ; i=position, that makes next element(i+1) larger than previous one(i) --different from permutation
	*/
	public class Subsets {
	public static void main(String[] args) {
	int[] S = {1, 2, 3};
	System.out.println(subsets(S));
	}
	public static ArrayList<ArrayList<Integer>> subsets(int[] S) {
	Arrays.sort(S);
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	ArrayList<Integer> list = new ArrayList<Integer>();
	subsetsHelper(result, list, S, 0);
	return result;
	}
	private static void subsetsHelper(ArrayList<ArrayList<Integer>> result,
	ArrayList<Integer> list, int[] s, int position) {
	result.add(new ArrayList<Integer>(list));
	for (int i = position; i < s.length; i++) {
	list.add(s[i]);
	subsetsHelper(result, list, s, i+1);
	list.remove(list.size() - 1);
	}
	}
	/**
	* My thought -- As I solve combination first and then solve subsets, I want to solve it by thought in combination,
	* Actually, subsets is more general problem. We need to think general problem first and then solve specific ones.
	* In addition, I solve combination use iterative but not recursive way which is simpler.
	* To get better remember --> use recursive
	*
	* Difference between subsets and combination
	* 1. int[] S not 1...n, the number may not start from 1 and continuous
	* 2. may solve using combination (n,1).. (n,n)
	*
	*/
	}

view raw Subsets.java hosted with ❤ by GitHub

NonRecursiveTraversal of BinaryTree (preorder, inorder and postorder) @LeetCode

Like title claims. Non Recursive way.

	package leetcode.tree;
	import java.util.ArrayList;
	import java.util.Stack;
	/**
	* @author jeffwan
	* @date Feb 9, 2014
	*
	* NonRecursiveTraversal
	* inorder and preorder are almost same, postorder is a little complicated
	* All use one stack, and postorder use another TreeNode head as parent pointer.
	*
	*/
	public class NonRecursiveTraversal {
	public ArrayList<Integer> preorderTraversal(TreeNode root) {
	ArrayList<Integer> list = new ArrayList<Integer>();
	Stack<TreeNode> stack = new Stack<TreeNode>();
	TreeNode node = root;
	while ( node != null || stack.size() > 0) {
	while (node != null) {
	stack.push(node);
	list.add(node.val);
	node = node.left;
	}
	if (stack.size() > 0) {
	node = stack.pop();
	node = node.right;
	}
	}
	return list;
	}
	public ArrayList<Integer> inorderTraversal(TreeNode root) {
	ArrayList<Integer> list = new ArrayList<Integer>();
	Stack<TreeNode> stack = new Stack<TreeNode>();
	TreeNode node = root;
	while (node != null || stack.size() > 0) {
	while(node != null) {
	stack.push(node);
	node = node.left;
	}
	if (stack.size() > 0) {
	node = stack.pop();
	list.add(node.val);
	node = node.right;
	}
	}
	return list;
	}
	/**
	* @date Feb 9, 2014
	*
	* Take Care: Different from Inorder and Preorder, postOrder will push root at first.
	* And then call next.left, we need to make sure it is not null. inorder and preorder, traversal already handle that.
	*
	* Could stack push a null value? -- Yes, stack will be [null]
	*
	* Pop condition:
	* next.left == null && next.right == null, which means it's leaf
	* parent will be push at the bottom of stack --> PostOrder. and then right child.
	*
	* next.left == head, next.right == head ---> check if next(stack peek) is the parent, also could be right child
	*/
	public ArrayList<Integer> postorderTraversal(TreeNode root) {
	ArrayList<Integer> list = new ArrayList<Integer>();
	Stack<TreeNode> stack = new Stack<TreeNode>();
	stack.push(root);
	TreeNode popped = root;
	if (root == null) {
	return list;
	}
	while (!stack.isEmpty()) {
	TreeNode next = stack.peek();
	if (next.left == popped || next.right == popped
	|| (next.left == null && next.right == null)) {
	next = stack.pop();
	list.add(next);
	popped = next;
	} else {
	if (next.right != null) {
	stack.push(next.right);
	}
	if (next.left != null) {
	stack.push(next.left);
	}
	}
	}
	return list;
	}
	/**************************** Recursive Way **************************/
	public ArrayList<Integer> preorderRecursiveTraversal(TreeNode root) {
	ArrayList<Integer> list = new ArrayList<Integer>();
	traversal(list, root);
	return list;
	}
	public void traversal(ArrayList<Integer> list, TreeNode node) {
	if (node == null) {
	return;
	}
	list.add(node.val);
	traversal(list, node.left);
	traversal(list, node.right);
	}
	private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int x) {val = x; };
	}
	}

view raw NonRecursiveTraversal.java hosted with ❤ by GitHub

Reverse Integer @LeetCode

Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

click to show spoilers.

Have you thought about this?

Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!

If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?

Throw an exception? Good, but what if throwing an exception is not an option? You would then have to re-design the function (ie, add an extra parameter).

	package leetcode.simpleCoding;
	/**
	* @author jeffwan
	* @date Feb 8, 2014
	*
	* Objective: write the simple and readable codes
	* There's no algorithm in this kind of problem but some tiny simple method. Our goal is to make it as clear as possible.
	* In addition, It's a good opportunity communicatting with interviewer about the overflow, 100 -- 001 (display).
	*
	* It's better to throw exception but not return -1 (Ambiguity)
	*/
	public class ReverseInteger {
	public static void main(String args[]) {
	// System.out.println(reverse3(1000000003)); overflow
	System.out.println(reverse(1000000003));
	// System.out.println(Integer.MAX_VALUE);
	// System.out.println(Integer.MIN_VALUE);
	}
	/**
	* Actually, we don't need to concern if a number if positive or not. It will always take the operator during operation.
	* If we don't care overflow problem, this solution will be very short.
	*/
	public static int reverse(int x) {
	int result = 0;
	int originalX = x;
	while (x != 0) {
	result = result * 10 + x % 10;
	x = x /10;
	}
	if ((originalX > 0 && result < 0) || (originalX < 0 && result > 0)) {
	return -1;
	}
	return result;
	}
	/**
	* Use mod to get every number and then reverse
	* Just use int without judging x == 0
	*/
	public static int reverse2(int x) {
	boolean isNegative = x < 0 ? true: false;
	x = Math.abs(x);
	int result = 0;
	while (x > 0) {
	result = result * 10 + x % 10;
	x = x / 10;
	}
	if (result < 0) { // no multioverflow?
	return -1;
	}
	if (isNegative) {
	return -result;
	}
	return result;
	}
	/**
	* Convert integer to string, use charAt changing brutely
	* Here I rely on function Integer.valueOf to solve the problem 100 --> 1 but not 001
	* Didn't sovle overflow problem -- but leetcode online judge accepted? can't believe
	* Overflow will remains in Integer.valueOf() which troughs exception that we can't handle like reverse2()
	*/
	public static int reverse3(int x) {
	if (x == 0) return 0;
	boolean isPositive = true;
	if (x < 0) {
	isPositive = false;
	}
	String str = Math.abs(x) + "";
	StringBuffer sb = new StringBuffer();
	for (int i = str.length() - 1; i >= 0; i--) {
	sb.append(str.charAt(i));
	}
	int result = Integer.valueOf(sb.toString());
	if(isPositive) {
	return result;
	} else {
	return -result;
	}
	}
	}

view raw ReverseInteger.java hosted with ❤ by GitHub

Combinations @LeetCode

Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

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

	package leetcode.combinations;
	import java.util.ArrayList;
	public class Combine {
	public static void main(String args[]) {
	System.out.println(combine(4,2));
	}
	/**
	* @date Feb 10, 2014
	*
	* Solution2:Recursive (same as subsets)
	* Difference: only list.size == k, output the result
	*
	*/
	public static ArrayList<ArrayList<Integer>> combine(int n, int k) {
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	ArrayList<Integer> list = new ArrayList<Integer>();
	combineHelper(result, list, n, k, 1);
	return result;
	}
	private static void combineHelper(ArrayList<ArrayList<Integer>> result,
	ArrayList<Integer> list, int n, int k, int position) {
	if (list.size() == k) {
	result.add(new ArrayList<Integer>(list));
	return;
	}
	for(int i=position; i<=n; i++) {
	list.add(i);
	combineHelper(result, list, n, k, i+1);
	list.remove(list.size() - 1);
	}
	}
	/**
	* Solution1: Iterative
	* eg: combine(6,3)
	* Fill in k element like [1,2,3] and then, this is one result, then go depth, [1,2,4] until [1,2,6]
	* [1,2,7]which will not meet a[i]-i <= n-k+1. then it changed to [1,3,7] ,next loop, it go back to normal [1,3,4]
	*
	* Most important condition
	* 1. a[i] < a[i+1] --> make no duplicate
	* 1. a[i]-i <= n-k+1; which means a[0] can't large than 4. if so, a[0]=5, a[1]=6, a[2]=? n=6. Important condition!
	*/
	public static ArrayList<ArrayList<Integer>> combine1(int n, int k) {
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	int i = 0;
	int[] a = new int[k];
	a[i] = 1;
	while(true) {
	if (a[i] - i <= n - k + 1) { // could go depth!
	if (i == k - 1) { // a is full -- find a result
	combine1Helper(result, a);
	a[i]++;
	} else { //not full
	i++;
	a[i] = a[i-1] + 1;
	}
	} else { // stop or go back
	if (i == 0) {
	return result;
	} else {
	a[--i] ++;
	}
	}
	}
	}
	private static void combine1Helper(ArrayList<ArrayList<Integer>> result, int[] a) {
	ArrayList<Integer> list = new ArrayList<Integer>();
	for(int x: a) {
	list.add(x);
	}
	result.add(list);
	}
	}

view raw Combine.java hosted with ❤ by GitHub

Sqrt(x) @LeetCode

Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

	package leetcode.binarySearch;
	/**
	* Solution: BinarySearch
	*
	* Tricky:
	* 1. Misunderstand the question, input 5,output 2; input 2,output 1. If not found, return the closest but not -1;
	* 2. I am not sure if 99 return 9 or 10, according to wrong answer, it seems like to be 9 even if 10 is closer.
	* 3. Input:2147395599, Output:2147395598, Expected:46339 the problem here is overflow x=500000 25000*25000<1000000
	* 4. we need to change mid * mid < target --> mid < target/mid if we use int !
	* 5. We could use long instead of int because of operation complexity of int
	* 6. to make it more efficient, the end should be x/2+1, squre(x/2+1) always >= square(x) !!!
	*
	* @author jeffwan
	*
	*/
	public class Sqrt {
	public int sqrt(int x) {
	int start, end, mid;
	start = 0;
	end = x / 2 + 1;
	while(start + 1 < end) {
	mid = start + (end - start) / 2;
	if (mid == x / mid) {
	return mid;
	} else if (mid < x / mid) {
	start = mid;
	} else {
	end = mid;
	}
	}
	if (start == x / start) {
	return start;
	}
	if (end == x / end) {
	return end;
	}
	return start;
	}
	// Use long to prevent overflow
	public int sqrt2(int x) {
	if (x < 0) {
	return -1;
	}
	long start, end, mid;
	start = 0;
	end = x ;
	while (start + 1 < end) {
	mid = start + (end - start) / 2;
	long square = mid * mid;
	if ((long)x == square) {
	return (int)mid;
	} else if ((long)x < square ) {
	end = mid;
	} else {
	start = mid;
	}
	}
	if ((long)x == start * start) {
	return (int)start;
	}
	return (int)start;
	}
	}

view raw Sqrt.java hosted with ❤ by GitHub