108、将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / 
   -3   9
   /   /
 -10  5

题解：

二叉搜索树就是二叉排序树，本题要求同时是平衡二叉树，所以可以采用分治的思想，类似二分查找。

/* C++ */

vector<int>& nums) /*nums首先是个引用，引用的东西就是vector这个容器的变量，容器内部存着整型数据*/

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 8  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 9  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10  * };
11  */
12 class Solution {
13 public:
14     TreeNode* createBST(vector<int>& nums,int start,int end) {
15         if(start>end) return nullptr; 
16         if(end==start){ //数组只有一个元素，返回这个节点
17             TreeNode* node = new TreeNode(nums[start]);
18             return node;
19         }else{
20             int mid=(start+end)/2;
21             TreeNode* node = new TreeNode(nums[mid]); //当前节点
22             node->left = createBST(nums,start,mid-1); //递归当前节点左边的数组
23             node->right = createBST(nums,mid+1,end); //递归当前节点右边的数组
24             return node;
25         }
26     }
27     TreeNode* sortedArrayToBST(vector<int>& nums){ 
28         return createBST(nums,0,nums.size()-1);
29     }
30 };

/* JavaScript */

slice() 方法可从已有的数组中返回选定的元素，arrayObject.slice(start,end)

 1 /**
 2  * Definition for a binary tree node.
 3  * function TreeNode(val, left, right) {
 4  *     this.val = (val===undefined ? 0 : val)
 5  *     this.left = (left===undefined ? null : left)
 6  *     this.right = (right===undefined ? null : right)
 7  * }
 8  */
 9 /**
10  * @param {number[]} nums
11  * @return {TreeNode}
12  */
13 var sortedArrayToBST = function(nums) {
14     if(nums.length === 0){
15         return null;
16     }else if(nums.length === 1){
17         return new TreeNode(nums[0]);
18     }else{
19         var mid = parseInt(nums.length/2); /* 利用parseInt()转换为整数 */
20         var root = new TreeNode(nums[mid]);
21         root.left = sortedArrayToBST(nums.slice(0,mid)); 
22         root.right = sortedArrayToBST(nums.slice(mid+1));
23         return root;
24     }
25 };