思路

题目分析

1. 本题题干给出了一个增序序列
2. 我们需要返回一棵按照上述序列组织的平衡二叉树，返回树根节点指针即可

• 方法一递归
  • 我们认为我们的递归函数功能为
    • 返回值表示以当前结点为根节点的平衡二叉树建立好
    • 参数中包含了当前根节点，当前根节点的所要处理的数据在nums数组中的左右边界
    • 函数体中需要我们从这个边界中取出中点的数值作为根节点数值
    • 然后递归左右子树建树
  • 这样我们只需要从根节点进行递归建树即可
• 方法二迭代
  • 迭代的方法同样是层序遍历的思路
  • 我们需要维护三个队列，结点队列、左边界队列、右边界队列
  • 这三个队列的功能就是维护了递归方法中的根节点、根节点对应的左边界、根节点对应的右边界
  • 通过层序访问的方式一层一层构建即可

方法一：递归

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param num int整型vector 
     * @return TreeNode类
     */
    TreeNode* sort(vector<int>& num, int l, int r) {
        if(num.size() == 0) return NULL;              // 如果num为空则返回NULL结束
        if(l > r) return NULL;                        // 如果界限l>r则退出返回NULL
        int m = ceil(1.0*(l+r)/2);                    // 按照题目的答案要求需要向上取整
        TreeNode* root = new TreeNode(num[m]);        // 对中间的值进行根节点建立
        root->left = sort(num, l, m-1);               // 依照上一步的根节点递归延伸左子节点
        root->right = sort(num, m+1, r);              // 依照上一步的根节点递归延伸右子节点
        return root;                                  // 返回建立好的当前root为根的树
    }
    
    TreeNode* sortedArrayToBST(vector<int>& num) {
        // write code here
        return sort(num, 0, num.size()-1);            // 从中间建立左右两边的树
    }
};

复杂度分析

• 时间复杂度：$O\left(N\right)O(N)$O(N)，所有节点都要访问处理一次
• 空间复杂度：$O\left(N\right)O(N)$O(N)，递归栈空间的使用，每个节点的函数调用都占用了一次递归栈空间

方法二：迭代

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.size() == 0) return nullptr;
        TreeNode* root = new TreeNode(0);        // 初始化根节点
        
        queue<TreeNode*> nodesQue;               // 存储我们构造的树的节点指针，每一个while循环出队入队树中一层的结点
        queue<int> lque;                         // 与上面的nodeQue对应的分界的左边界
        queue<int> rque;                         // 与上面的nodeQue对应的分界的右边界
                                                 // 同时入队三项：
        nodesQue.push(root);                     // 当前结点
        lque.push(0);                            // 当前结点分界的左边界
        rque.push(nums.size() - 1);              // 当前结点分界的右边界
        
        while(!nodesQue.empty()){                // 判断结点队列是否为空
                                                 // 读取三项内容：
            TreeNode* temp = nodesQue.front();   // 结点队列最前面的一项结点指针
            int l = lque.front();                // 与上面结点指针对应的分界左边界
            int r = rque.front();                // 与上面结点指针对应的分界右边界
            
            int m = (l+r+1)/2;                   // 计算中点位置（上取整）
            
            nodesQue.pop();                      // 同时将前面三个读到的内容出队
            lque.pop();
            rque.pop();
            
            temp->val = nums[m];                 // 修正中间平衡的根节点的值
            
            if(l < m) {                          // 必须l和m不同且 l<m 才允许继续添加结点
                temp->left = new TreeNode(0);    // 添加一个新的待定值的左结点
                nodesQue.push(temp->left);       // 同时三个元素入队：结点+左边界+右边界
                lque.push(l);
                rque.push(m-1);
            }
            if(r > m) {                          // 必须r和m不同且 r>m 才允许继续添加结点
                temp->right = new TreeNode(0);   // 添加一个新的待定值的右结点
                nodesQue.push(temp->right);      // 同时三个元素入队：结点+左边界+右边界
                lque.push(m+1);
                rque.push(r);
            }
        }
        
        return root;
    }
};

复杂度分析

• 时间复杂度：$O\left(N\right)O(N)$O(N)，所有的结点都要访问一次
• 空间复杂度：$O\left(logN\right)O(logN)$O(logN)，队列所用的最大额外空间也只是树最大一层的结点数量，是$O\left(logN\right)O(logN)$O(logN)级别