题解 | #将升序数组转化为平衡二叉搜索树#

将升序数组转化为平衡二叉搜索树
题解一：二分+递归
题解思路： 利用BST中序遍历为升序序列的特性。
BST中序遍历：

思路分析： 为了保持平衡，每次选择区间的中间值作为根节点。
递归分析：
递归边界： (left > right) 返回NULL；
递归过程： 选取中间值作为根节点，root = mid = (left+right+1)/2; 递归构建左右子树。

复杂度分析：
时间复杂度：O(N) 节点数N
空间复杂度：O(logN)

实现如下：

class Solution {
public:
    /**
     *
     * @param num int整型vector
     * @return TreeNode类
     */
    TreeNode* creat_BST(vector<int>& num,int left,int right){
        if(left>right) return NULL;  // 递归边界
        int mid = (left+right+1)/2;   //选取中间位置的值作为根节点
        TreeNode* root = new TreeNode(num[mid]);  //创建树的根节点
        root -> left  = creat_BST(num, left, mid-1);  // 构建左子树
        root-> right = creat_BST(num, mid+1, right);  // 构建右子树
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& num) {
        // write code here
        if(num.size() ==0 ) return NULL; // 如果数组为空，返回空树
        return creat_BST(num, 0, num.size()-1); //  递归建树
    }
};

题解二： 迭代
题解思路： 与题解一相同，不过将递归转为迭代的写法.依然是分割的思想。
分析： 使用一个栈来保存左右子树边界，一个栈用来保存遍历的节点。
复杂度度分析：
时间复杂度：O(N)，遍历整个节点数N
空间复杂度：O(logN)
实现如下：

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& num) {
        if(num.size() ==0 ) return NULL;
        stack<TreeNode*> node_st; // 用来保存构造的节点
        stack<int> lr_index; // 用来保存边界
        TreeNode* root = new TreeNode(0); //根节点入栈
        node_st.push(root);
        lr_index.push(0);  // 将左边界入栈
        lr_index.push(num.size()-1); // 右边界入栈
        while(node_st.size()){
            int right = lr_index.top();lr_index.pop();  //取出左边界
            int left = lr_index.top();lr_index.pop();   //取出右边界
            int mid = (right+left+1)/2; //取中间值作为根节点的值
            TreeNode* tmp = node_st.top();   //取出当前节点
            node_st.pop();
            tmp->val = num[mid];   //将中间值赋予当前节点的值

            //划分左子树
            if(left<= mid-1){
                tmp->left = new TreeNode(0);
                node_st.push(tmp->left);
                lr_index.push(left);
                lr_index.push(mid-1);
            }
            //划分右子树
            if(right>= mid+1){
                tmp->right = new TreeNode(0);
                node_st.push(tmp->right);
                lr_index.push(mid+1); //
                lr_index.push(right);
            }
        }
        return root;
    }
};