[LeetCode 108] Convert Sorted Array to Binary Search Tree

Question

link

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

Stats

Frequency	3
Difficulty	2
Adjusted Difficulty	2
Time to use	--------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

My first understanding of this question is wrong.

A BST does not necessarily have to fill in left side of the leaf as muc has possible. I was confusing “balanced binary tree” with “left-balanced binary tree”.

A balanced binary tree is commonly defined as a binary tree in which the depth of the left and right subtrees of every node differ by 1 or less

A left-balanced binary tree is a balanced binary tree where the left sub-tree of each node is filled before the right sub-tree

Solution

Then this question become straight-forward.

Code

public TreeNode sortedArrayToBST(int[] num) {
    if (num.length == 0) return null;
    return helper(num, 0, num.length - 1);
}

public TreeNode helper(int[] num, int start, int end) {
    if (start > end) return null;
    int mid = (start + end) / 2;
    TreeNode node = new TreeNode(num[mid]);
    node.left = helper(num, start, mid - 1);
    node.right = helper(num, mid + 1, end);
    return node;
}