力扣1008题：从前序遍历构建二叉搜索树 - 递归解法详解

内容简介

本文详细解析了力扣第1008题"从前序遍历序列构建二叉搜索树"的递归解法。通过利用BST的性质和前序遍历的特点，实现了从数组到BST的高效转换。这种方法时间复杂度为O(n^2)，是理解BST构建过程的经典解法。文章包含完整注释代码、算法思路讲解和复杂度分析。

算法思路

‌1.递归构建‌：利用前序遍历第一个元素作为根节点

‌2.分割数组‌：找到第一个大于根节点的元素作为右子树起点

‌3.递归处理‌：分别构建左右子树

‌4.边界处理‌：处理空数组和单元素数组的特殊情况

完整代码（带注释）

class Solution {
public:
    // 递归辅助函数：根据前序遍历数组构建BST
    TreeNode* bst_preorder(vector<int>& preorder, int l, int r) {
        if (r - l <= 0) return nullptr;  // 空区间返回空指针
        
        TreeNode* root = new TreeNode(preorder[l]);  // 前序第一个元素作为根节点
        if (r - l == 1) return root;  // 只有一个元素直接返回
        
        int mid = l;  // 初始化分割点
        // 寻找第一个大于根节点值的元素位置
        for (int i = l + 1; i < r; i++) {
            if (preorder[i] > root->val) {
                mid = i;
                break;
            }
        }
        // 如果没有更大的元素，则所有元素都在左子树
        if (mid == l) mid = r;
        
        // 递归构建左右子树
        root->left = bst_preorder(preorder, l + 1, mid);
        root->right = bst_preorder(preorder, mid, r);
        
        return root;
    }
    
    // 主函数：从前序遍历构建BST
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        return bst_preorder(preorder, 0, preorder.size());   
    }
};

复杂度分析

‌时间复杂度‌：最坏O(n^2)，当树退化为链表时

‌空间复杂度‌：O(n)，递归栈空间和树节点存储

优化方向

‌单调栈法‌：可以将时间复杂度优化到O(n)

‌排序+哈希‌：先排序得到中序，再利用前序和中序构建

‌迭代实现‌：用栈代替递归，避免递归带来的额外开销

总结

本文提供的递归解法是从前序遍历构建BST的直观方法，通过利用BST的性质分割数组，实现了高效的树构建。理解这种解法有助于掌握BST的特性和递归算法的应用。

参考：力扣1008题 解题思路和步骤 C++实现带注释