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