sortedArrayToBST

sorted_array_to_bst.rb

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val)
#         @val = val
#         @left, @right = nil, nil
#     end
# end

# @param {Integer[]} nums
# @return {TreeNode}
=begin
Runtime: 68 ms, faster than 96.20% of Ruby online submissions for Convert Sorted Array to Binary Search Tree.
Memory Usage: 80.5 MB, less than 50.00% of Ruby online submissions for Convert Sorted Array to Binary Search Tree.
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/submissions/
=end
def sorted_array_to_bst(nums)
    return nil if nums.size.zero?
    mid = nums.size/2
    ans = TreeNode.new(nums[mid])
    ans.left = sorted_array_to_bst(nums[0...mid])
    ans.right = sorted_array_to_bst(nums[mid+1..-1])
    ans
end

sortedArrayToBST.go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/submissions/
 Runtime: 108 ms, faster than 41.94% of Go online submissions for Convert Sorted Array to Binary Search Tree.
Memory Usage: 137.8 MB, less than 100.00% of Go online submissions for Convert Sorted Array to Binary Search Tree.
 */



func sortedArrayToBST(nums []int) *TreeNode {
    if 0 == len(nums){
        return nil
    }
    mediana := 0
    if 0 == len(nums)%2{
        mediana = (len(nums))/2
    }else{
        mediana = len(nums)/2
    }
    val := nums[mediana]
    left,right := nums[0:mediana], nums[mediana+1:]
    lft := sortedArrayToBST(left)
    rgt := sortedArrayToBST(right)
    ans := TreeNode{Val: val, Left: lft, Right: rgt}
    
    
    return &ans
    
}

sortedArrayToBST.js

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/submissions/
 Runtime: 72 ms, faster than 32.85% of JavaScript online submissions for Convert Sorted Array to Binary Search Tree.
Memory Usage: 37.6 MB, less than 34.61% of JavaScript online submissions for Convert Sorted Array to Binary Search Tree.
 */
var sortedArrayToBST = function(nums) {
    if( 0 == nums.length) return null;
    let middle = parseInt(nums.length/2)
    let ans = new TreeNode(nums[middle])
    ans.left = sortedArrayToBST(nums.slice(0,middle))
    ans.right = sortedArrayToBST(nums.slice(middle+1))
    return ans;
};

sortedArrayToBST.php

<?php
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
/*
* https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/submissions/
* Runtime: 16 ms, faster than 73.33% of PHP online submissions for Convert Sorted Array to Binary Search Tree.
* Memory Usage: 18.1 MB, less than 100.00% of PHP online submissions for Convert Sorted Array to Binary Search Tree.
*/
class Solution {

    /**
     * @param Integer[] $nums
     * @return TreeNode
     */
    function sortedArrayToBST($nums) {
        if(0 == count($nums)){
            return null;
        }
        $mid = intval(count($nums)/2);
        $ans = new TreeNode($nums[$mid]);
        $ans->left = $this->sortedArrayToBST(array_slice($nums,0,$mid));
        $ans->right = $this->sortedArrayToBST(array_slice($nums,$mid+1));
        return $ans;
        
    }
}

sortedArrayToBST.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
'''
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/submissions/
Runtime: 84 ms, faster than 23.70% of Python3 online submissions for Convert Sorted Array to Binary Search Tree.
Memory Usage: 16.2 MB, less than 6.45% of Python3 online submissions for Convert Sorted Array to Binary Search Tree.
'''
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if 0 == len(nums): return None
        mid = int(len(nums)/2)
        answer = TreeNode(nums[mid])
        answer.left = self.sortedArrayToBST(nums[0:mid])
        answer.right = self.sortedArrayToBST(nums[mid+1:])
        return answer
        

sortedArrayToBST_bound_checking.go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
Runtime: 96 ms, faster than 78.92% of Go online submissions for Convert Sorted Array to Binary Search Tree.
Memory Usage: 222.3 MB, less than 100.00% of Go online submissions for Convert Sorted Array to Binary Search Tree.
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/submissions/
 */

func sortedArrayToBST(nums []int) *TreeNode {
    if 0 == len(nums){
        return nil
    }
    mid := len(nums)/2
    var left,right * TreeNode
    
    if 0 == mid {
        left = nil
    }else  {
        left = sortedArrayToBST(nums[0:mid])
    }
    
    if 0 == mid {
        right = nil
    }else if len(nums) <= mid + 1{
        right = nil
    }else{
        right = sortedArrayToBST(nums[mid+1:len(nums)])
    }
    
    return  & TreeNode{Val: nums[mid], Left: left, Right: right }
}

sortedArrayToBST_short.go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
Runtime: 104 ms, faster than 56.18% of Go online submissions for Convert Sorted Array to Binary Search Tree.
Memory Usage: 137.9 MB, less than 100.00% of Go online submissions for Convert Sorted Array to Binary Search Tree.
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/submissions/
 */



func sortedArrayToBST(nums []int) *TreeNode {
    if 0 == len(nums){
        return nil
    }
    mid := len(nums)/2
    return  & TreeNode{Val: nums[mid], Left: sortedArrayToBST(nums[0:mid]), Right: sortedArrayToBST(nums[mid+1:])  }
}

@tsov_pro Roman Covanyan
https://leetcode.com/covrom/
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/discuss/391081/why-do-golang-in-this-algorithm-realization-twice-slowly-than-python-or-js
boundary checking and write barrier checking in 11 version of go