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