###### tags: `Leetcode` `easy` `tree` `divide and conquer` `python` `c++`

# 108. Convert Sorted Array to Binary Search Tree

## [題目出處:] https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

## 題目:
Given an integer array nums where the elements are sorted in **ascending order**, convert it to a **height-balanced** binary search tree.

A **height-balanced** binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

## 解題想法:
因為題目給的是已經排好的數組
由最中間的數字當作root，遞迴即可

## Python:

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if not nums:
            return None
        mid=len(nums)//2
        root=TreeNode(nums[mid])
        root.left=self.sortedArrayToBST(nums[:mid])
        root.right=self.sortedArrayToBST(nums[mid+1:])
        return root

nums=[-10,-3,0,5,9]
result=Solution()
ans=result.sortedArrayToBST(nums)
ans.printTree()

## C++:

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

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

void InsertLeft(TreeNode* root, int data){
    TreeNode *tmp=root;
    if (tmp->left != nullptr)
        InsertLeft(root->left, data);
    else{
        TreeNode *new_left= new TreeNode(data);
        tmp->left=new_left;
    }
}

void InsertRight(TreeNode*root, int data){
    TreeNode *tmp=root;
    if (tmp->right != nullptr)
        InsertRight(root->right, data);
    else{
        TreeNode *new_right= new TreeNode(data);
        tmp->right=new_right;
    }
}

void PrintTree(TreeNode* root){
    TreeNode *tmp=root;
    vector<int> res;
    queue<TreeNode*> que;
    que.push(root);
    while (!que.empty()){
        TreeNode *curRoot=que.front(); que.pop();
        res.push_back(curRoot->val);
        if (curRoot->left)
            que.push(curRoot->left);
        if (curRoot->right)
            que.push(curRoot->right);
    }
    for (int i=0; i<res.size(); i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;
}

class Solution{
public:
    TreeNode* sortedArrayToBST(vector<int>& nums){
        if (nums.empty())
            return nullptr;
        int mid = nums.size()/2;
        TreeNode *root=new TreeNode(nums[mid]);
        vector<int> left(nums.begin(), nums.begin()+mid); //nums[:mid]
        vector<int> right(nums.begin()+mid+1, nums.end()); //nums[mid+1:]
        root->left=sortedArrayToBST(left);
        root->right=sortedArrayToBST(right);
        return root;
    }
};


int main(){

    Solution res;
    vector<int> nums={-10,-3,0,5,9};
    TreeNode *ans=res.sortedArrayToBST(nums);
    PrintTree(ans);
    return 0;
}