[LeetCode] 108. Convert Sorted Array to Binary Search Tree

Posted on | In

Problem

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

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.

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:

1
2
3
4
5
      0
     / \
   -3   9
   /   /
 -10  5

Explanation

  1. If we use in-order traversal of a binary search tree, then we can get a sorted array. So, if we have a sorted array, then the middle element must be the root of the tree, and we can divide the array into two parts from 0 to mid-1 to find the left-subtree and mid+1 to array.length-1 to find the right-subtree. So, this problem can be sorted using binary search method.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode helper(int[] nums, int left, int right) {
        if (left > right) return null;
        int mid = left + (right-left)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, left, mid-1);
        root.right = helper(nums, mid+1, right);
        return root;
    }
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) return null;
        return helper(nums, 0, nums.length-1);
    }
}