LeetCode [108] Convert Sorted Array to Binary Search Tree

108. Convert Sorted Array to Binary Search Tree

Easy

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:

      0
     / \
   -3   9
   /   /
 -10  5

//C++: 21ms
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int n = nums.size();
        return dfs(nums, 0, n-1);
    }
    TreeNode* dfs(vector<int>& nums, int start, int end){
        if(start>end) return NULL;
        int mid = (start+end)/2;
        int root_v = nums[mid];
        TreeNode* node = new TreeNode(root_v);
        node->left = dfs(nums, start, mid-1);
        node->right = dfs(nums, mid+1, end);
        return node;
    }
};

//Java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length-1);
    }
    
    TreeNode helper(int[] nums, int l, int r){
        if(l>r) return null;
        int m = (l+r)/2;
        TreeNode p = new TreeNode(nums[m]);
        p.left = helper(nums, l, m-1);
        p.right = helper(nums, m+1, r);
        return p;
    }
}