【树】Convert Sorted Array to Binary Search Tree

题目:

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

思路:

找到数组的中间数据作为根节点,小于中间数据的数组来构造作为左子树,大于中间数据的数组来构造右子树。

/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var sortedArrayToBST = function(nums) {
var len=nums.length;
if(len==0){
return null;
}
return BuildTree(nums,0,len-1);
}; function BuildTree(nums,s,e){
if(s>e){
return null;
}
if(s==e){
return new TreeNode(nums[s]);
}
var middle=(s+e)/2;
var rootval=nums[middle];
var root=new TreeNode(rootval);
root.left=BuildTree(nums,s,middle-1);
root.right=BuildTree(nums,middle+1,e);
return root;
}
上一篇:eclips运行generatorConfig.xml文件生成代码


下一篇:POJ 1699 Best Sequence dfs