leetcode Question 23: Convert Sorted Array to Binary Search Tree

Convert Sorted Array to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Analysis:

Because the requirement "height balanced", this problem becomes relative easy.
Just recursively use the middle element in the array as the root node of the current tree(sub tree).

Code(C++):

/**
 * 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* cbst(vector<int> &num, int st, int ed){
        if (st>ed){
            return NULL;
        }else{
            int mid = st+(ed-st)/2;
            TreeNode *bst=new TreeNode(num[mid]);
            bst->left = cbst(num,st,mid-1);
            bst->right = cbst(num,mid+1,ed);
            return bst;
        }
    }

    TreeNode *sortedArrayToBST(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (num.size()==0){return NULL;}
        return cbst(num,0,num.size()-1);
    }
};

Code(Python):

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param num, a list of integers
    # @return a tree node
    def bst(self, num, st, ed):
        if st > ed:
            return None
        mid = st + (ed - st)/2
        left = self.bst(num, st, mid - 1)
        root = TreeNode(num[mid])
        right = self.bst(num, mid + 1, ed)
        root.left = left
        root.right = right
        return root
    
    def sortedArrayToBST(self, num):
        n = len(num)
        if n == 0:
            return None
        return self.bst(num, 0, n-1)