package leetcode.easy;

/**

 * Definition for a binary tree node. public class TreeNode { int val; TreeNode

 * left; TreeNode right; TreeNode(int x) { val = x; } }

 */

public class ConvertSortedArrayToBinarySearchTree {

	public TreeNode sortedArrayToBST(int[] nums) {

		if (0 == nums.length) {

			return null;

		}

		TreeNode root = new TreeNode(nums[nums.length / 2]);

		root.left = sortedArrayToBST(java.util.Arrays.copyOfRange(nums, 0, nums.length / 2));

		root.right = sortedArrayToBST(java.util.Arrays.copyOfRange(nums, nums.length / 2 + 1, nums.length));

		return root;

	}

	private static void transLevel(TreeNode root) {

		java.util.LinkedList<TreeNode> queue = new java.util.LinkedList<>();

		if (null == root) {

			return;

		} else {

			System.out.print(root.val + " ");

			queue.offer(root);

			while (!queue.isEmpty()) {

				root = queue.pop();

				if (root.left != null) {

					System.out.print(root.left.val + " ");

					queue.offer(root.left);

				}

				if (root.right != null) {

					System.out.print(root.right.val + " ");

					queue.offer(root.right);

				}

			} // end of the while

		} // end of the if

	}

	@org.junit.Test

	public void test() {

		int[] nums = { -10, -3, 0, 5, 9 };

		TreeNode root = sortedArrayToBST(nums);

		transLevel(root);

	}

}