Question

Formatted question description: https://leetcode.ca/all/108.html

108	Convert Sorted Array to Binary

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

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

@tag-tree

Algorithm

The root node should be the middle point of the ordered array, separated from the middle point into two left and right ordered arrays, and find out the left and right child nodes whose middle point is the original middle point.

Code

Java

import java.util.Arrays;

public class Convert_Sorted_Array_to_Binary_Search_Tree {

    public static void main(String[] args) {
        Convert_Sorted_Array_to_Binary_Search_Tree out = new Convert_Sorted_Array_to_Binary_Search_Tree();
        Solution s = out.new Solution();

        int[] a = {1, 2, 3, 4, 5};

        int[] b = Arrays.copyOfRange(a, 0, a.length);
        System.out.println(Arrays.toString(b));

//		b = Arrays.copyOfRange(a, 2, 1); // error, must to > from

        b = Arrays.copyOfRange(a, 2, 2); // ok, empty array returned
        System.out.println("a, 2, 2: " + Arrays.toString(b));

//		b = Arrays.copyOfRange(a, -1, 10); // error, out of boundary
//		System.out.println("a, -1, 10" + Arrays.toString(b));

        b = Arrays.copyOfRange(a, a.length, a.length); // ok, empty array returned
        System.out.println("a, a.length, a.length: " + Arrays.toString(b));

    }


	/**
	 * Definition for binary tree
	 * public class TreeNode {
	 *     int val;
	 *     TreeNode left;
	 *     TreeNode right;
	 *     TreeNode(int x) { val = x; }
	 * }
	 */
    public class Solution {
        public TreeNode sortedArrayToBST(int[] nums) {

            if (nums == null || nums.length == 0) return null;

            return dfs(nums, 0, nums.length - 1);
        }

        TreeNode dfs(int[] nums, int left, int right) {
            if (left > right) return null;
            int mid = left + (right - left) / 2;
            TreeNode cur = new TreeNode(nums[mid]);
            cur.left = dfs(nums, left, mid - 1);
            cur.right = dfs(nums, mid + 1, right);
            return cur;
        }
    }
}

All Problems

All Solutions