108. Convert Sorted Array to Binary Search Tree

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

My Solution(C/C++)

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    //vector<TreeNode *> sortedArrayToBST(vector<int> &nums) {
    TreeNode * sortedArrayToBST(vector<int> &nums) {
        if (nums.size() == 0) {
            return NULL;
        }
        int begin = 0;
        int end = nums.size() - 1;
        //int mid;
        vector<TreeNode *> node;
            /*mid = (begin + end) / 2;*/
        creatNode(nums, begin, end, node);
        TreeNode *result = node[0];
        for (int i = 1; i < node.size(); i++) {
            addNodeToBST(node[i], result);
        }
        return result;
    }
    void print_TreeNode(TreeNode *result, int level) {  //打印二叉树
        if (!result) {
            return;
        }
        for (int i = 0; i < level; i++) {
            printf("-");
        }
        printf(" %d\n", result->val);
        print_TreeNode(result->left, level + 1);
        print_TreeNode(result->right, level + 1);
    }
private:
    void creatNode(vector<int> &nums, int begin, int end, vector<TreeNode *> &node) {  //将数组转换成待插入节点数组
        if (begin > end) {
            return;
        }
        int mid = (begin + end) / 2;
        node.push_back(new TreeNode(nums[mid]));
        creatNode(nums, begin, mid - 1, node);
        creatNode(nums, mid + 1, end, node);
    }
    void addNodeToBST(TreeNode *node, TreeNode *result) {  //将节点插入到二叉查找树中
        if (node->val < result->val) {
            if (result->left) {
                addNodeToBST(node, result->left);
            }
            else {
                result->left = node;
            }
        }
        else if (node->val >= result->val) {
            if (result->right) {
                addNodeToBST(node, result->right);
            }
            else {
                result->right = node;
            }
        }
    }
};

int main() {
    //vector<TreeNode *> node;
    Solution s;
    vector<int> nums;
    nums.push_back(-10);
    nums.push_back(-3);
    nums.push_back(0);
    nums.push_back(5);
    nums.push_back(9);
    TreeNode *result;
    result = s.sortedArrayToBST(nums);
    //for (int i = 0; i < node.size(); i++) {
    //  printf("%d->", node[i]->val);
    //}
    int level = 1;
    s.print_TreeNode(result, level);
    return 0;
}

My Solution(Python)

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

class Solution:
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if nums == []:
            return []
        begin, end, BST_nums = 0, len(nums) - 1, []
        self.sortedBSTArray(nums, begin, end, BST_nums)
        root = TreeNode(BST_nums[0])
        result = root
        for i in range(1, len(BST_nums)):
            node = TreeNode(BST_nums[i])
            self.insertToBST(root, node)
        return result

    def sortedBSTArray(self, nums, begin, end, BST_nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if begin > end:
            return
        mid = (begin + end) // 2
        BST_nums.append(nums[mid])
        self.sortedBSTArray(nums, begin, mid - 1, BST_nums)
        self.sortedBSTArray(nums, mid + 1, end, BST_nums)

    def insertToBST(self, root, node):
        """
        :param root: TreeNode 满足左子树小于根节点，右子树大于根节点
        :param node: TreeNode: node->val = ((int) in nums) 每次要插入到二叉排序（查找）树的节点
        :return: TreeNode 插入新的节点后的新的二叉排序（查找）树
        """
        if not root:
            return
        if node.val < root.val:
            if root.left:
                self.insertToBST(root.left, node)
            else:
                root.left = node
        else:
            if root.right:
                self.insertToBST(root.right, node)
            else:
                root.right = node

Reference

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

class Solution:
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        
        if len(nums)==0:
            return None
        return self.createTree(nums, 0, len(nums)-1)
        
    def createTree(self, nums, low, high):
        if low<=high:
            mid = (low+high)//2
            node = TreeNode(nums[mid])
            node.left = self.createTree(nums, low, mid-1)
            node.right = self.createTree(nums, mid+1, high)
            return node
        return None