[LeetCode]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.
【分析】
二分法,以中间元素i为根节点[start,i-1]递归构建左子树,[i+1,end]递归构建右子树
【代码】
/*********************************
* 日期:2014-12-28
* 作者:SJF0115
* 题目: 108.Convert Sorted Array to Binary Search Tree
* 来源:https://oj.leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
* 结果:AC
* 来源:LeetCode
* 总结:
**********************************/
#include <iostream>
#include <queue>
#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:
TreeNode *sortedArrayToBST(vector<int> &num) {
if(num.size() == 0){
return NULL;
}//if
return SortedArrayToBST(num,0,num.size()-1);
}
private:
TreeNode* SortedArrayToBST(vector<int> &num,int start,int end){
if(start > end){
return NULL;
}//if
int mid = (start + end) / 2;
// 根节点
TreeNode *root = new TreeNode(num[mid]);
// 左子树
TreeNode *leftSubTree = SortedArrayToBST(num,start,mid-1);
// 右子树
TreeNode *rightSubTree = SortedArrayToBST(num,mid+1,end);
// 连接
root->left = leftSubTree;
root->right = rightSubTree;
return root;
}
};
// 层次遍历
vector<vector<int> > LevelOrder(TreeNode *root) {
vector<int> level;
vector<vector<int> > levels;
if(root == NULL){
return levels;
}
queue<TreeNode*> cur,next;
//入队列
cur.push(root);
// 层次遍历
while(!cur.empty()){
//当前层遍历
while(!cur.empty()){
TreeNode *p = cur.front();
cur.pop();
level.push_back(p->val);
// next保存下一层节点
//左子树
if(p->left){
next.push(p->left);
}
//右子树
if(p->right){
next.push(p->right);
}
}
levels.push_back(level);
level.clear();
swap(next,cur);
}//while
return levels;
}
int main() {
Solution solution;
vector<int> num = {1,3,5,6,7,13,20};
TreeNode* root = solution.sortedArrayToBST(num);
vector<vector<int> > levels = LevelOrder(root);
for(int i = 0;i < levels.size();i++){
for(int j = 0;j < levels[i].size();j++){
cout<<levels[i][j]<<" ";
}
cout<<endl;
}
}
【错解】
class Solution {
public:
TreeNode *sortedArrayToBST(vector<int> &num) {
if(num.size() == 0){
return NULL;
}//if
return SortedArrayToBST(num,0,num.size()-1);
}
private:
TreeNode* SortedArrayToBST(vector<int> num,int start,int end){
int len = end - start;
if(len < 0){
return NULL;
}//if
int mid = (start + end) / 2;
// 根节点
TreeNode *root = new TreeNode(num[mid]);
// 左子树
TreeNode *leftSubTree = SortedArrayToBST(num,start,mid-1);
// 右子树
TreeNode *rightSubTree = SortedArrayToBST(num,mid+1,end);
// 连接
root->left = leftSubTree;
root->right = rightSubTree;
return root;
}
};
解析:
注意到这一句代码:TreeNode* SortedArrayToBST(vector<int> num,int start,int end)
传递num是值传递,不是引用传递,所以每次递归调用SortedArrayToBST函数时,它会再次复制这个大vector。所以在递归过程中,这种行为将花费很大内存。