现在的位置: 首页 > 综合 > 正文

Convert Sorted Array to Binary Search Tree

2018年04月12日 ⁄ 综合 ⁄ 共 694字 ⁄ 字号 评论关闭

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

 

比较简单,直观的就是每次将数组二分分别建立左子树和右子树就可以了。

 

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 #define vi vector<int>
#define tn TreeNode 
class Solution {
public:
   tn* sortedArrayToBST(vi& num)
{
    	int n=num.size();
    	if (n==0 )
		return NULL;
	int mid=n>>1;
	tn* root= new tn(num[mid]);
    	root->left=construct(num,0,mid-1);
   	root->right=construct(num,mid+1,n-1);

	return root;
}
tn* construct(vi& num,int start,int end)
{
	if(end<start)
		return NULL;
	int mid=start+((end-start)>>1);
	tn* root=new tn(num[mid]);
	root->left=construct(num,start,mid-1);
	root->right=construct(num,mid+1,end);
	return root;
}
};

抱歉!评论已关闭.