【题目】

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。所以在递归过程中,这种行为将花费很大内存。

[LeetCode]Convert Sorted Array to Binary Search Tree